Langage indexé

Les deux langages suivants sont indexés, et ne sont pas context-free :

• ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$ ^[3]
• ${\displaystyle \{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}}$ ^[2]

Les deux langages suivant sont également indexés, mais ne sont pas légèrement sensibles au contexte d'après la caractérisation de Gazdar :

• ${\displaystyle \{a^{2^{n}}|n\geq 0\}}$ ^[2]
• ${\displaystyle \{www|w\in \{a,b\}^{+}\}}$ ^[3]

Enfin, le langage suivant

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

n'est pas indexé^[6] :

Hopcroft et Ullman, dans des notes (p. 394-395) dans leur livre de 1979^[7]. considèrent que les langages indexés forment une classe « naturelle » de langages parce qu'ils admettent plusieurs définitions équivalents ; ce sont :

• les langages reconnus par les automates à piles emboîtées uni-directionnels de Alfred Aho^[8] ;
• les langages engendrés par les macro-grammaires de Michael J. Fischer^[9] ;
• les langages reconnus par les automates à piles de piles de Sheila A. Greibach^[10] ;
• les langages définis par une caractérisation algébrique donnée par Tom Maibaum (en)^[11].

Takafumi Hayashi^[12] a généralisé le lemme d'itération pour les langages algébriques aux grammaires indexées. Dans la direction opposée, Robert H. Gilman^[6] donne un lemme de réduction pour les langages indexés.

• Portail de la linguistique
• Portail de l'informatique théorique