Problem członkostwa dla niektórych klas gramatyki nieograniczonej

Rozważ dowolną bezkontekstową gramatykę nad alfabetem . Do produkcji tej gramatyki dodaj dwie stałe produkcje bezkontekstowe : i \ overline {1} 1 \ rightarrow \ epsilon . Nazwij wynikową gramatykę G ^ P oznaczającą „ G uzupełniony o produkcje 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$

Czy można podać algorytm, który przyjmuje gramatykę $G^P$ i ciąg $s$ ponad $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$ i decyduje, czy $s \in \mathcal{L}(G^ P)$ ?

Ta klasa gramatyk jest nierozstrzygalna. Oto przybliżony pomysł na temat tego, jak używać go do emulacji maszyn Turinga.

W każdym punkcie wyglądałoby obecne częściowo częściowo rozwinięte słowo

Tutaj:

• $[\mbox{tape to the left}]$ , po zastosowaniu , zawiera tylko znaki i .$P$$\overline0$$\overline1$
• $[\mbox{tape to the right}]$ , po zastosowaniu , zawiera tylko znaki i .$P$$0$$1$
• $[\mbox{head}]$ to pojedynczy nieterminal, który koduje zarówno stan głowy, jak i znak w pozycji głowy.

Załóżmy, że głowa znajduje się w stanie , a znak pod głową to . Wtedy głowa jest reprezentowana przez nieterminalny . Jeśli trzeba przejść do stanu , zastąpić obecny znak , i przejść w lewo, istnieją dwa przejścia i . Jeśli zamiast tego trzeba przejść w prawo, istnieją dwa przejścia i$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$. W pewnym sensie głowa musi „odgadnąć” postać w kierunku, w którym się porusza, tworząc pasującą postać. Jeśli zgadywanie jest błędne, niezmiennik na lub zostałby naruszony i nigdy się nie odzyskał.$[\mbox{tape to the left}]$$[\mbox{tape to the right}]$

Gdy maszyna zatrzymuje się, głowa powinna „zużyć” taśmę po obu stronach, „zgadując” i wytwarzając pasujące znaki. Następnie powinno wygenerować puste słowo. W rezultacie puste słowo byłoby członkiem takiej gramatyki wtedy i tylko wtedy, gdy odpowiednia maszyna Turinga zatrzyma się.