Mitgliedschaftsproblem für bestimmte Klassen uneingeschränkter Grammatiken

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$$\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$$P$$\overline{0} 0 \rightarrow \epsilon$$\overline{1} 1 \rightarrow \epsilon$$G^P$$G$$P$

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 ?$G^P$$s$$\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$$s \in \mathcal{L}(G^ P)$

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

Hier:

• $[\mbox{tape to the left}]$$P$$\overline0$$\overline1$
• $[\mbox{tape to the right}]$$P$$0$$1$
• $[\mbox{head}]$

$S$$i\in\{0,1\}$$S_i$$T$$j$$S_i\rightarrow0T_0j$$S_i\rightarrow1T_1j$$S_i\rightarrow\overline jT_0\overline0$$S_i\rightarrow\overline jT_1\overline 1$$[\mbox{tape to the left}]$$[\mbox{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.