Quelle est l'importance du contexte sensible (type 1) langues?

Question

Voyant que la hiérarchie type Chomsky 3 langues peut être reconnu par une machine d'état sans mémoire externe (c.-à- un automate fini), le type 2 par une machine d'état avec un seul pile (soit un automate de poussée vers le bas) et de type 0 par une machine d'état avec deux piles (ou, de manière équivalente, une bande, comme cela est le cas pour les machines de Turing), comment s'adapter langues de type 1 dans cette image? Et quels sont les avantages que cela apporte pour déterminer qu'une langue est non seulement Type 0 mais le type 1?

Answer 1

Les langues contextuelles sont exactement les langues qui peuvent être reconnues par une machine de Turing en utilisant l'espace linéaire et non-déterminisme. Vous pouvez simuler une telle machine de Turing en utilisant le temps exponentielle, de sorte que vous pouvez reconnaître une telle langue dans le temps exponentielle. Prenez note que le problème de la reconnaissance des langues contextuelles est $ PSPACE $ -complete, ce qui signifie que nous sommes assez sûrs que vous ne pouvez pas faire mieux que le temps exponentiel.

En comparant ce type 0 à langues, cela signifie que vous pouvez au moins dire quelque chose combien de temps il faut pour reconnaître la langue. Un type 0 langue ne peut pas être même décidable:. La langue de toutes les machines de Turing que l'arrêt est un type 0 langue, mais comme la reconnaissance de cette langue est exactement le problème de l'arrêt, il est décidable

grammaires sensibles au contexte ne sont pas très utiles dans la pratique. Context- libre sont intuitifs à travailler avec, mais comme les exemples sur Wikipédia montrent , context- sensible gRAMMAIRES très vite devenu assez désordonné. Les programmes utilisant l'espace polynomiale sont beaucoup plus faciles à concevoir (et les garanties de la PSPACE $ $ l'existence d'une CSG équivalent qui est seulement polynomiale plus grande que l'utilisation de l'espace de votre algorithme).

La raison de leur existence est qu'ils forment une extension très naturelle de grammaires hors contexte (vous permettent de déterminer le contexte qui productions sont valides). Cela aura probablement inspiré Chomsky pour les définir et de les nommer les langues de type 1. Rappelez-vous que cette définition a été faite avant que les ordinateurs sont devenus aussi vite qu'ils le sont aujourd'hui. Il est plus intéressant de théoriciens du langage formel que pour les programmeurs

grammaires encore plus étrange Unrestricted obtenir: il n'y a plus une notion de « expansion » a elle et non-terminal remplacer par une production, en fonction éventuellement le contexte. Vous êtes autorisé à modifier librement le contexte. Cela rend encore moins sans restriction grammaires intuitive de travailler avec:. Les programmes sont équivalents et beaucoup plus intuitive

Answer 2

D'une manière générale, vous voulez généralement de connaître la plus petite classe à laquelle une langue donnée $ L $ appartient. Ceci est parce que les classes plus petites peuvent être reconnues / acceptées / générées par des mécanismes plus simples (automates, grammaires, expressions régulières, etc.), ce qui est souhaitable.

Par exemple, la classe des langues régulières a bon propriétés de fermeture, et donné une DFA $ \ mathcal {A} $, vous pouvez tester en temps linéaire qu'un mot appartient à $ L (\ mathcal {A}) $. En revanche, avec une machine de Turing vous avez besoin de temps linéaire suffit de lire la sortie, ce qui se produit généralement avant il commence effectivement le traitement.

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

Selon Wikipedia , défini Chomsky grammaires sensibles au contexte (type 1) pour décrire la syntaxe naturelle langues. Ceci est un autre bit que d'autres classes de langues, qui ont été introduites pour décrire les familles de chaînes qui ont été utilisées en mathématiques (par exemple, la syntaxe des formules arithmétiques) au lieu des langues naturelles (par exemple, la syntaxe d'une phrase grammaticalement correcte en anglais) .

Answer 3

Dans les langues sans contexte, en tout point de l'analyse syntaxique d'entrée, l'automate est dans un état défini par la pile. Chaque production a le même comportement en consommant l'entrée, peu importe où il est utilisé.

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

• a: L'entrée consommée par A est complètement 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 disjoint de l'entrée consommée par B

Cela implique que ce qui suit ne se produit jamais:

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

Contrastant que, dans les langues contextuelles, le comportement de chaque production dépend de l'endroit où il est utilisé, de sorte que l'entrée consommée dans une production n'est pas une sous-langue des plus profonds de la pile (en fait, le traitement avec une pile ne fonctionnerait pas). Et nous avons cette possibilité d peut se produire.

Dans le monde réel, un cas où quelque chose comme dénotant gras , texte en italique et surlignés un serait logique langue contextuelle avec ces balises html et les laisser se chevauchent, comme "Ceci est un texte mixte balises chevauchement ." Notez que pour analyser cela et trouver si toutes les balises de départ correspondent aux balises de fin, un PDA ne le fera pas parce qu'il est pas hors-contexte, mais un LBA facilement faire.

Answer 4

Propriétés de fermeture

de toutes les classes de langue de la hiérarchie de Chomsky, seules les langues régulières et sensibles au contexte sont fermés sous complémentation . D'où c'est une sorte de caractéristique unique des langues contextuelles.

Contrairement aux langues sans contexte, CS sont également fermés par intersection et lecture aléatoire produit.

Answer 5

Toute langue qui est de type 1 peut être reconnu par une machine de Turing qui utilise uniquement l'espace linéaire (soi-disant linéaires automates borné).

Answer 6

langues de type 1 peuvent être décidées par linéaire borné automates, qui sont des machines de Turing non déterministe qui ne peut utiliser une partie de la bande dont la taille est linéaire à la taille d'entrée.

Answer 7

La hiérarchie de Chomsky classifie plus de langues grammaires. Cependant, il n'a pas été conçu pour avoir quelque chose à voir avec le nombre de bandes un automate devrait avoir à reconnaître, comme vous le suggérez de type 2 et 3, même s'il y a une sorte de machine de Turing qui fait que pour les grammaires de type 1.

Vous devriez également noter que les langues de type 0 grammaires ne sont pas tous reconnus par une machine de Turing, mais ils ne peuvent être dénombrées par une telle machine: type 0 moyen récursive dénombrable, et les machines de Turing reconnaître que les langues récursives.

Answer 8

Utilisation du langage de programmation moderne propose contextuelle tout le temps; ils tombent dans un sous-ensemble qui peut être efficacement décidé.

Les exemples sont le nom et l'analyse du type et de l'inférence de type.

Answer 9

Beaucoup d'autres ont mentionné que les langues de type 1 sont celles qui peuvent être reconnus par des automates linéaires borné. Le problème est décidable pour arrêt des automates linéaires borné, qui signifie à son tour beaucoup d'autres propriétés qui sont informatiquement indécidable pour les langues reconnues par Machines de tournage sont décidables pour les langues de type 1.

Il est vrai que la preuve que le problème de l'arrêt est décidable pour les automates linéaires borné repose sur le fait que, avec une quantité finie de la bande, ils ne peuvent entrer dans un nombre fini d'états, donc s'ils n'arrêtent pas dans de nombreuses étapes que vous connaissez ils sont en boucle et ne jamais arrêter. Cette preuve s'applique sur le plan technique à tous les ordinateurs réels (qui ont aussi la mémoire finie), mais qui ne sont pas d'un avantage pratique pour résoudre le problème de l'arrêt pour les programmes qui leur sont destinés.