Comment prouver qu'une langue est hors contexte?

26

Il existe de nombreuses techniques pour prouver qu'une langue n'est pas sans contexte, mais comment puis-je prouver qu'une langue est sans contexte?

Quelles techniques existe-t-il pour le prouver? De toute évidence, une façon consiste à présenter une grammaire sans contexte pour la langue. Existe-t-il des techniques systématiques pour trouver une grammaire sans contexte pour une langue donnée?

Pour les langages réguliers, il existe des moyens systématiques de dériver un automate grammatical / à états finis: par exemple, le théorème de Myhill-Nerode fournit un moyen. Existe-t-il une technique correspondante pour les langages hors contexte?


Ma motivation ici est (espérons-le) de construire une question de référence qui contient une liste de techniques qui sont souvent utiles, lorsque j'essaie de prouver qu'une langue donnée est hors contexte. Puisque nous avons ici de nombreuses questions qui en sont des cas particuliers, il serait bien que nous puissions documenter l'approche générale ou les techniques générales que l'on peut utiliser face à ce type de problème.

DW
la source
Permettez-moi de laisser ma note habituelle: lorsque vous fournissez une grammaire sans contexte pour la langue en question, vous avez besoin d'une preuve d'exactitude qui peut rendre l'approche plutôt compliquée.
Raphael
Pour en faire une bonne question de référence que nous pouvons lancer sur les dumpers à problèmes, pourriez-vous ajouter une réponse sur l'élaboration de grammaires et d'automates, peut-être avec un exemple chacun? Merci!
Raphael
Jusqu'à ce que le matériel soit déplacé ici, notez que Rick Decker et babou ont collecté des idiomes sans contexte typiques lors d'une question en double .
Raphael

Réponses:

13

Une approche pratique qui, dans de nombreux exemples, fonctionne [mais pas toujours, je sais] essaie de trouver la structure d'imbrication des chaînes dans le langage. Les "dépendances imbriquées" doivent être générées en même temps dans différentes parties de la chaîne.

Nous avons également la boîte à outils de base :

  1. concaténation: si vous pouvez diviser la langue en deux parties consécutives utilisez cette productionSS1S2

  2. union: divisé en parties disjointesSS1S2

  3. itération:SS1Sε

Exemple 1

Voici un exemple pour la nidification (merci Raphael).

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

Remplacez par . Nous pouvons maintenant déposer dans des conditions.n2ln

Remplacez par (confus? est «oh» et non «zéro»). Appliquer des outils pour l'union. Nous travaillons avec ici. Aussi ssi k = s + o et s > 0s est une nouvelle variable. Remplacez k par s + o .k > o  ou  k < o o k > o k > okok>o or k<ook>ok>ok=s+os>0sks+o

L1={bs+oal(bc)ma2lbol,m,o,sN,s>0,m2}

Quelques réécritures simples.

L1={bbsboalbcbc(bc)m(aa)lbol,m,o,sN}

Nous voyons maintenant la structure d'imbrication et commençons à construire une grammaire.

, T b U , U b U ε (voir: concaténation et itération ici)S1TVTbUUbUε

(nous générons des o b des deux côtés)VbVbWo b

WaWaaX

, Y b c b c , Z b c Z εXYZYbcbcZbcZε

Exemple 2

K={akblcml=m+k}

Une première réécriture "évidente".

K={akbm+kcmm,k0}={akbmbkcmm,k0}

Dans le linguistice, cela s'appelle la «dépendance inter-série»: l'entrelacement (généralement) indique fortement l'absence de non-contexte. Bien sûr, m + k = k + m et nous sommes sauvés.k,m,k,mm+k=k+m

K={akbk+mcmm,k0}={akbkbmcmm,k0}

avec productions , X a X b ε , Y b Y c εSXYXaXbεYbYcε

De même K={akblcmm=k+l}={akblclckk,l0}

avec productions , X b X c εSaScXXbXcε


Commentaire final: ces techniques vous aident à trouver une grammaire sans contexte candidate qui, nous l'espérons, reconnaîtra votre langue. Une preuve d'exactitude peut encore être nécessaire, pour garantir que la grammaire fonctionne vraiment pour reconnaître votre langue (ni plus ni moins).

Hendrik Jan
la source
11

Il existe une caractérisation des CFL qui peut être utile, le théorème de Chomsky-Schützenberger .

Langue Dyck

Soit un alphabet. Nous définissons le Dyck -language D T( T T ) * de T par le libre contexte grammaire G = ( { S } , T T , δ , S ) avec δ donné parTDT(TT^)TG=({S},TT^,δ,S)δ

.SaSa^Sε,aT

Théorème de Chomsky-Schützenberger

est hors contexte si et seulement s'il y aLΣ

  • un alphabet ,T
  • une langue régulière etR(TT^)
  • homomorphisme ψ:(TT^)Σ

pour que

.L=ψ(DTR)

Notez que l'homomorphisme est étendu aux mots (symbole par symbole) puis aux langues (mot par mot).

Exemple

Considérons . AvecL={anbncmn,mN

  • (et, canoniquement, T = { ] , } ),T={[,}T^={],}
  • etR=L([])
  • ψ(x)={a,x=[b,x= ]ε,x=c,x= 

le théorème implique que est sans contexte, en particulier depuisL

.DTR={[n]nmmn,mN}

Exemple 2

Montrer que est sans contexte.L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

Ici, nous avons besoin d'un type de parenthèses pour , une pour b c , une pour b et une autre utilisée pour modéliser les b qui causent k o . Nous utilisonsabcbbko

  • ,T={[,,,<}
  • etR=L(<+>+[++])L([++]<+>+)
  • ψ(x)={b,x{,,<}a,x=[aa,x= ]bc,x=ε,else

et appliquer le théorème. Pour voir que , nous ne devons plus que le fait que les symboles correspondants (par exemple , [ et ] ) doivent se produire aussi souvent en tout w D T . En ajoutant cette contraint aux expressions régulières que nous avons définies R par, nous obtenonsL=ψ(DTR)[]wDTR

DTR={<p>po[lmm]lop1,o0,l0,m2} {}

et avec cela

ψ(DTR)={bp+oal(bc)ma2lbop1,o0,l0,m2} {}={bkal(bc)manbok,l,m,n,oN,k>o,2l=n,m2} {}=L.

To grammars and automata

If we want to have an automaton or grammar in the end, we have some more work ahead of us.

  • Towards an automaton, construct the NPDA for DT and an NFA for R. The former is standard and we have algorithms for the latter, provided the language is given in a suitable representation (see also here). Intersection both is another standard construction and ψ can be applied to every transition individually.

  • Towards a grammar, build one for R (again, should be standard), take the one for DT and intersect them. Then apply ψ to the rule set (symbol for symbol).

Arguably, this is easy since algorithmic; the complexity lies in finding suitable T, R and ψ. I don't know if this approach is (often) simpler than constructing PDA/grammars directly but it may allow to focus on the important features of the language at hand. Try for yourself!

Raphael
la source
It is undecidable whether any given language is context-free.
reinierpost