Mitgliedschaftsproblem für bestimmte Klassen uneingeschränkter Grammatiken

9

Betrachten Sie eine beliebige kontextfreie Grammatik über dem Alphabet { 0 , 1 , ¯ 0 , ¯ 1 } . Fügen Sie den Produktionen dieser Grammatik zwei feste, nicht kontextfreie Produktionen P hinzu : ¯ 0 0 ϵ und ¯ 1 1 ϵ . Nennen Sie die resultierende Grammatik G P und stehen Sie für " G erweitert mit den Produktionen P ".G{0,1,0¯,1¯}P0¯0ϵ1¯1ϵGPGP

Ist es möglich, einen Algorithmus anzugeben, der eine Grammatik und eine Zeichenfolge s über { 0 , 1 , ¯ 0 , ¯ 1 } nimmt und entscheidet, ob s L ( G P ) ist ?GPs{0,1,0¯,1¯}sL(GP)

Amit. S.
quelle
Interessanterweise scheint die Antwort "Nein" zu sein, aber wenn regulär ist, ist es auch L ( G P ) . Im Wesentlichen ein NFA für L ( G ) kann in einen für transformiert werden L ( G P ) durch iteratives Addieren ε -Übergänge ( s , ε , t ) , wann immer Sie haben Pfade ( s , ˉ 0 , p , 0 , t ) ,L(G)L(GP)L(G)L(GP)ϵ(s,ϵ,t) oder ( s , ϵ , p , ϵ , t ) und schließlich durchführen(s,0¯,p,0,t),(s,0¯,p,ϵ,q,0,t),(s,1¯,p,1,t),(s,1¯,p,ϵ,q,1,t)(s,ϵ,p,ϵ,t) Beseitigung. ϵ
Klaus Draeger
Ja, das ist wahr. Tatsächlich ergab sich die Frage aus einem Problem bei der Programmanalyse (auf Lebendigkeit basierende Speicherbereinigung). Wir haben das Problem umgangen, indem wir die CFG an eine stark reguläre Grammatik angenähert haben (Mohri-Nederhoff-Transformation) und dann die Vereinfachungen an der resultierenden NFA genau so vorgenommen haben, wie Klaus Draeger es erwähnt. P
Amit.

Antworten:

5

Diese Klasse von Grammatiken ist unentscheidbar. Hier ist eine grobe Vorstellung davon, wie man damit Turing-Maschinen emuliert.

An jedem Punkt würde das aktuelle teilweise erweiterte Wort so aussehen

[tape to the left][head][tape to the right]

Hier:

  • [tape to the left]P0¯1¯
  • [tape to the right]P01
  • [head]

Si{0,1}SiTjSi0T0jSi1T1jSij¯T00¯Sij¯T11¯[tape to the left][tape to the right]

Wenn die Maschine anhält, sollte der Kopf sein Klebeband auf beiden Seiten "verbrauchen", indem er "errät" und übereinstimmende Zeichen erzeugt. Danach sollte es ein leeres Wort erzeugen. Infolgedessen wäre ein leeres Wort genau dann ein Mitglied einer solchen Grammatik, wenn die entsprechende Turing-Maschine anhält.

abacabadabacaba
quelle
NN
@ Amit.SI lieferte einige weitere Erklärungen zu Übergängen in der Antwort.
Abacabadabacaba