Llenguatge indexat

Els llenguatges indexats son una classe de llenguatge formal descoberta per Alfred Aho.^[1] Es generen amb les gramàtiques indexades i es poden reconèixer pels autòmats amb pila anidada.^[2]

Son un subconjunt propi dels llenguatges sensibles al context. És una classe de llenguatge força important pel processament de llenguatge natural, ja que son generalitzacions de llenguatges lliures del context amb millor computabilitat.

Gerald Gazdar i Vijay-Shanker van definir els llenguatges lleugerament lliures del context també dites gramàtiques indexades lineals, que tenen restriccions addicionals a les gramàtiques indexades.^[3][3]

Els següents llenguatges son indexats, però no son lliures del context:^[2][4]

${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$

${\displaystyle \{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}}$

Els dos següents llenguatges son indexats però no son ni lleugerament lliures del context:^[2][4]

${\displaystyle \{a^{2^{n}}|n\geq 0\}}$

${\displaystyle \{www|w\in \{a,b\}^{+}\}}$

I per últim, aquest llenguatge no és indexat:^[5]

${\displaystyle \{(ab^{n})^{n}|n\geq 0\}}$