Langage contextuel - Context-sensitive language

Dans la théorie des langages formels , un langage contextuel est un langage qui peut être défini par une grammaire contextuelle (et de manière équivalente par une grammaire non contractante ). Sensible au contexte est l'un des quatre types de grammaires de la hiérarchie de Chomsky .

Propriétés de calcul

Du point de vue informatique, un langage contextuel est équivalent à une machine de Turing non déterministe bornée linéaire , également appelée automate borné linéaire . C'est une machine de Turing non déterministe avec une bande de cellules uniquement , où est la taille de l'entrée et est une constante associée à la machine. Cela signifie que chaque langage formel qui peut être décidé par une telle machine est un langage contextuel, et que chaque langage contextuel peut être décidé par une telle machine. ${\displaystyle kn}$${\style d'affichage n}$${\style d'affichage k}$

Cet ensemble de langages est également connu sous le nom de NLINSPACE ou NSPACE ( O ( n )), car ils peuvent être acceptés en utilisant l'espace linéaire sur une machine de Turing non déterministe. La classe LINSPACE (ou DSPACE ( O ( n ))) est définie de la même manière, sauf en utilisant une machine de Turing déterministe . Il est clair que LINSPACE est un sous-ensemble de NLINSPACE , mais on ne sait pas si LINSPACE = NLINSPACE .

Exemples

L'un des langages contextuels mais non contextuels les plus simples est : le langage de toutes les chaînes consistant en n occurrences du symbole "a", puis n "b", puis n "c" (abc, aabbcc , aaabbbcccc, etc.). Un sur-ensemble de cette langue, appelé la langue de Bach, est défini comme l'ensemble de toutes les cordes où "a", "b" et "c" (ou tout autre ensemble de trois symboles) se produisent également souvent (aabccb, baabcaccb, etc. ) et est également contextuelle. ${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$

L peut être montré comme un langage contextuel en construisant un automate linéaire borné qui accepte L . On peut facilement montrer que le langage n'est ni régulier ni sans contexte en appliquant les lemmes de pompage respectifs pour chacune des classes de langage à L .

De la même manière:

${\displaystyle L_{Croix}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}$est une autre langue contextuelle ; le commençant par deux grammaires sans contexte peut être facilement projeté la grammaire contextuelle correspondante générer des formes phrastiques dans les formats et puis en les complétant avec une production de permutation comme un nouveau symbole de départ et de sucre syntaxique standard. ${\displaystyle a^{m}C^{m}}$${\displaystyle B^{n}d^{n}}$${\displaystyle CB\rightarrow CB}$

${\displaystyle L_{MUL3}=\{a^{m}b^{n}c^{mn}:m\geq 1,n\geq 1\}}$est une autre langue contextuelle (le « 3 » dans le nom de cette langue signifie un alphabet ternaire ); c'est-à-dire que l'opération « produit » définit un langage contextuel (mais la « somme » définit uniquement un langage sans contexte comme la grammaire et le montre). En raison de la propriété commutative du produit, la grammaire la plus intuitive pour est ambiguë. Ce problème peut être évité en considérant une définition plus restrictive du langage, par exemple . Celui-ci peut être spécialisé vers et, à partir de celui-ci, vers , , etc. ${\displaystyle S\rightarrow aSc|R}$${\displaystyle R\rightarrow bRc|bc}$${\style d'affichage L_{MUL3}}$${\displaystyle L_{ORDMUL3}=\{a^{m}b^{n}c^{mn}:1<m<n\}}$${\displaystyle L_{MUL1}=\{a^{mn}:m>1,n>1\}}$${\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}$${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}$

${\displaystyle L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}}$est un langage contextuel. La grammaire contextuelle correspondante peut être obtenue comme une généralisation des grammaires contextuelles pour , , etc. ${\displaystyle L_{Carré}=\{w^{2}:w\in \Sigma ^{*}\}}$${\displaystyle L_{Cube}=\{w^{3}:w\in \Sigma ^{*}\}}$

${\displaystyle L_{EXP}=\{a^{2^{n}}:n\geq 1\}}$ est un langage contextuel.

${\displaystyle L_{PRIMES2}=\{w:|w|{\mbox{ est premier }}\}}$est un langage contextuel (le "2" dans le nom de ce langage signifie un alphabet binaire). Cela a été prouvé par Hartmanis en utilisant des lemmes de pompage pour les langues régulières et sans contexte sur un alphabet binaire et, après cela, en esquissant un automate multibande linéaire borné acceptant . ${\style d'affichage L_{PRIMES2}}$

${\displaystyle L_{PRIMES1}=\{a^{p}:p{\mbox{ est premier }}\}}$est une langue contextuelle (le "1" dans le nom de cette langue signifie un alphabet unaire). Ceci a été crédité par A. Salomaa à Matti Soittola au moyen d'un automate linéaire borné sur un alphabet unaire (pages 213-214, exercice 6.8) et aussi à Marti Penttonen au moyen d'une grammaire contextuelle également sur un alphabet unaire (Voir : Langages formels par A. Salomaa, page 14, exemple 2.5).

Un exemple de langage récursif qui n'est pas sensible au contexte est tout langage récursif dont la décision est un problème EXPSPACE -difficile, disons, l'ensemble de paires d' expressions régulières équivalentes avec exponentiation.

Propriétés des langages contextuels

• L'union, l'intersection, la concaténation de deux langues contextuelles est contextuelle, de même que le Kleene plus d'une langue contextuelle est contextuelle.
• Le complément d'un langage contextuel est lui-même contextuel, un résultat connu sous le nom de théorème d'Immerman-Szelepcsényi .
• L'appartenance à une chaîne dans un langage défini par une grammaire contextuelle arbitraire, ou par une grammaire contextuelle déterministe arbitraire, est un problème PSPACE-complet .

Voir également

• Automate linéaire borné
• Liste des générateurs d'analyseurs pour les langages contextuels
• Hiérarchie de Chomsky
• Langues indexées - un sous-ensemble strict des langues contextuelles
• Hiérarchie de déversoir

Les références

• Sipser, M. (1996), Introduction à la théorie du calcul , PWS Publishing Co.