Langue indexée - Indexed language

Les langages indexés sont une classe de langages formels découverts par Alfred Aho ; ils sont décrits par des grammaires indexées et peuvent être reconnus par des automates à pile imbriquée .

Les langues indexées sont un sous - ensemble approprié des langues contextuelles . Ils sont qualifiés de famille abstraite de langages (de plus un AFL complet) et satisfont donc à de nombreuses propriétés de fermeture. Cependant, ils ne sont pas fermés par intersection ou complément.

La classe des langues indexées a une importance pratique dans le traitement du langage naturel en tant que généralisation informatiquement abordable des langues sans contexte , car les grammaires indexées peuvent décrire de nombreuses contraintes non locales se produisant dans les langues naturelles.

Gerald Gazdar (1988) et Vijay-Shanker (1987) ont introduit une classe de langage légèrement contextuelle désormais connue sous le nom de grammaires indexées linéaires (LIG). Les grammaires indexées linéaires ont des restrictions supplémentaires par rapport à IG. Les LIG sont faiblement équivalents ( générent la même classe de langage) que les grammaires arborescentes adjacentes .

Exemples

Les langages suivants sont indexés, mais ne sont pas hors contexte :

${\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\}}$

Ces deux langues sont également indexées, mais ne sont même pas légèrement contextuelles selon la caractérisation de Gazdar :

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

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

En revanche, la langue suivante n'est pas indexée :

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

Propriétés

Hopcroft et Ullman ont tendance à considérer les langages indexés comme une classe « naturelle », puisqu'ils sont générés par plusieurs formalismes, tels que :

• Les grammaires indexées d' Aho
• Automates à pile imbriquée à sens unique d' Aho
• Les macrogrammaires de Fischer
• Les automates de Greibach avec des piles de piles
• Caractérisation algébrique de Maibaum

Hayashi a généralisé le lemme de pompage aux grammaires indexées. Inversement, Gilman donne un "lemme rétrécissant" pour les langues indexées.

Voir également

• Hiérarchie de Chomsky
• Grammaire indexée
• Langage légèrement contextuel

Les références

Liens externes

• Chapitre "NLP in Prolog" sur les grammaires et langages indexés