Llenguatge indexat

De Viquipèdia
Salta a la navegació Salta a la cerca

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]

Exemples[modifica]

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

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

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

Referències[modifica]

  1. Aho, Alfred V. «Indexed Grammars—An Extension of Context-Free Grammars». J. ACM, 15, 4, 1968-10, pàg. 647–671. DOI: 10.1145/321479.321488. ISSN: 0004-5411.
  2. 2,0 2,1 2,2 Hall., Partee, Barbara. Mathematical methods in linguistics. Dordrecht: Kluwer Academic, 1990. ISBN 9027722447. 
  3. 3,0 3,1 Laura., Kallmeyer,. Parsing beyond context-free grammars. Heidelberg: Springer, 2010. ISBN 9783642148460. 
  4. 4,0 4,1 Gazdar, Gerald. Applicability of Indexed Grammars to Natural Languages (en en). Dordrecht: Springer Netherlands, 1988, p. 69–94. DOI 10.1007/978-94-009-1337-0_3. ISBN 9789400913370. 
  5. Gilman, Robert H. «A shrinking lemma for indexed languages». Theoretical Computer Science, 163, 1, 30-08-1996, pàg. 277–281. DOI: 10.1016/0304-3975(96)00244-7. ISSN: 0304-3975.