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 . Nazwij wynikową gramatykę oznaczającą „ uzupełniony o produkcje ”. $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)$ ?

context-free decidability

— Amit. S.
źródło

Co ciekawe, choć wydaje się, że odpowiedź brzmi „nie”, myślę, że jeśli

L (G)

$L(G)$ jest regularne, to również

L (G^{P})

$L(G^P)$ . Zasadniczo NFA dla

L (G)

$L(G)$ można przekształcić w jeden dla

L (G^{P})

$L(G^P)$ , iteracyjnie dodając

ϵ

$\epsilon$ -transitions

(s, ϵ, t)

$(s,\epsilon,t)$ ilekroć masz ścieżki

(s, \bar{0}, p, 0, t), (s, \bar{0}, p, ϵ, q, 0, t), (s, \bar{1}, p, 1, t), (s, \bar{1}, p, ϵ, q, 1, t)

$(s,\bar{0},p,0,t),(s,\bar{0},p,\epsilon,q,0,t),(s,\bar{1},p,1,t),(s,\bar{1},p,\epsilon,q,1,t)$ lub

(s, ϵ, p, ϵ, t)

$(s,\epsilon,p,\epsilon,t)$ , a na koniec wykonanie eliminacji

ϵ

$\epsilon$ .

— Klaus Draeger

Tak, to prawda. W rzeczywistości pytanie powstało w wyniku analizy programu (zbieranie śmieci na podstawie żywotności). Obejściliśmy ten problem, przybliżając CFG do bardzo regularnej gramatyki (transformacja Mohri-Nederhoffa), a następnie wykonując uproszczenia

P

$P$ na powstałym NFA dokładnie tak, jak wspomina Klaus Draeger.

— Amit.

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

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

$[\mbox{tape to the left}][\mbox{head}][\mbox{tape to the right}]$

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ę.

— abacabadabacaba
źródło

Nie jestem pewien, czy rozumiem twoją redukcję. Oto moja wątpliwość: jeśli dana maszyna Turinga ma stany , to czy liczba nieograniczonych produkcji wymaganych do emulacji maszyny Turinga nie jest związana z ? Ale mój problem pozwala tylko na dwie stałe, nieograniczone produkcje.

N

$N$

N

$N$

— Amit.

@ Amit.SI podał więcej wyjaśnień dotyczących przejść w odpowiedzi.

— abacabadabacaba