Quelle est la signification des langues contextuelles (Type 1)?

Voyant que, dans la hiérarchie de Chomsky, les langues de type 3 peuvent être reconnues par une machine à états dépourvue de mémoire externe (c'est-à-dire un automate fini), le type 2 par une machine à états à pile unique (un automate à pile) et le type 0 par une machine d'état à deux piles (ou, de manière équivalente, une bande, comme c'est le cas pour Turing Machines), comment les langues de type 1 s'intègrent-elles dans cette image? Et quels avantages apporte-t-il pour déterminer qu'une langue n'est pas seulement du type 0 mais du type 1?

$PSPACE$

En comparant cela aux langues de type 0, cela signifie que vous pouvez au moins dire quelque chose sur le temps qu'il faut pour reconnaître la langue. Un langage de type 0 n’est peut-être même pas décidable: le langage de toutes les machines Turing qui s’arrête est un langage de type 0, mais comme reconnaître ce langage est exactement le problème qui s’arrête, il n’est pas décidable.

$PSPACE$

La raison de leur existence est qu’elles forment une extension très naturelle des grammaires sans contexte (vous autorisez le contexte à déterminer quelles productions sont valides). Cela aura probablement incité Chomsky à les définir et à les nommer langues de type 1. Rappelez-vous que cette définition a été faite avant que les ordinateurs ne deviennent aussi rapides qu’ils le sont aujourd’hui: ils intéressent davantage les théoriciens du langage formel que les programmeurs.

Les grammaires illimitées deviennent encore plus étranges: il n’est plus question d’étendre un non-terminal et de le remplacer par une production, éventuellement en fonction du contexte. Vous êtes également autorisé à modifier librement le contexte. Cela rend les grammaires illimitées encore moins intuitives: les programmes sont équivalents et beaucoup plus intuitifs.

$L$

$\mathcal{A}$$L(\mathcal{A})$

En bref, pour les petites classes, vous avez besoin de moins de puissance de calcul pour résoudre le problème de savoir si un mot appartient à la langue.

Selon Wikipedia , Chomsky a défini des grammaires contextuelles (type 1) décrivant la syntaxe des langues naturelles. C'est un peu différent des autres classes de langages, introduites pour décrire les familles de chaînes utilisées en mathématiques (par exemple, la syntaxe des formules arithmétiques) au lieu des langages naturels (par exemple, la syntaxe d'une phrase grammaticalement correcte en anglais) .

Dans les langages sans contexte, à tout moment de l'analyse des entrées, l'automate est dans un état défini par sa pile. Chaque production a le même comportement en consommant l'intrant, peu importe où il est utilisé.

Cela conduit à la propriété intéressante que chaque production génère un sous-langage de celui généré par ceux qui sont plus profonds dans la pile. Ainsi, pour chaque paire A et B de productions générées et consommées sur une entrée particulière, nous avons trois cas possibles:

• a: l'entrée consommée par A est entièrement contenue dans l'entrée consommée par B; ou
• b: l'entrée consommée par A contient complètement l'entrée consommée par B; ou
• c: l'entrée consommée par A est complètement disjointe de l'entrée consommée par B.

Cela implique que les événements suivants ne se produisent jamais:

• d: l'entrée consommée par A chevauche partiellement l'entrée consommée par B.

Contrairement à cela, dans les langages contextuels, le comportement de chaque production dépend de l’utilisation qui en est faite, de sorte que l’intrant consommé dans une production n’est pas un sous-langage de ceux qui se trouvent plus loin dans la pile (en fait, le traiter avec une la pile ne fonctionnerait pas). Et nous avons cette possibilité d peut arriver.

Dans le monde réel, un langage sensible au contexte aurait du sens, ce qui revient à dire <b> texte en gras </ b>, <i> texte en italique </ i> et <u> texte souligné </ u> avec Ces balises HTML et laissez-les se chevaucher, comme "Ceci est un texte <u> avec des balises <i> mixtes </ u> qui se chevauchent </ i>." Observez cela pour analyser cela et trouver si toutes les balises de départ correspondent aux balises de fin, un PDA ne le fera pas car il n’est pas dépourvu de contexte, mais un LBA le fera facilement.

Propriétés de fermeture

De toutes les classes de langue de la hiérarchie de Chomsky, seuls les langages réguliers et sensibles au contexte sont fermés sous complément . C'est donc une sorte de caractéristique unique des langages contextuels.

Contrairement aux langages sans contexte, les CS sont également fermés sous les produits d'intersection et de mélange .

Toute langue de type 1 peut être reconnue par une machine de Turing utilisant uniquement des espaces linéaires (appelés automates linéaires bornés).

Type 1 languages can be decided by linear bounded automata, which are non-deterministic Turing machines that may only use a portion of the tape whose size is linear to the input size.

The Chomsky hierarchy classifies grammars more than languages. However it was not designed to have something to do with the number of tapes a automaton should have to recognize it, as you suggested for Type 2 and 3, even if there is a kind of Turing machine that does that for Type-1 grammars.

You should also note that the languages of Type-0 grammars are not all recognized by a Turing machine, but they only can be enumerated by such a machine: Type-0 means recursively enumerable, and Turing machines only recognize recursive languages.

Modern programming language use context-sensitive features all the time; they fall into a subset that can efficiently be decided.

Examples are name and type analysis and type inference.

Many others have mentioned that Type-1 languages are those that can be recognised by linear bounded automata. The halting problem is decidable for linear bounded automata, which in turn means many other properties that are computationally undecidable for languages recognised by Turning Machines are decidable for Type-1 languages.

Admittedly the proof that the halting problem is decidable for linear bounded automata relies on the fact that with a finite amount of tape they can only enter a finite number of states, so if they don't halt within that many steps you know they're looping and won't ever halt. This proof technically applies to all actual computers (which also have finite memory), but that isn't of any practical benefit in solving the halting problem for the programs that run on them.