Biorąc pod uwagę PDA M taki, że L (M) jest w DCFL konstruuj DPDA N, tak że L (N) = L (M)

Czy można zbudować algorytm, który przyjmuje jako dane wejściowe automat do przesuwania wraz z obietnicą, że język zaakceptowany przez ten automat L ( M ) jest deterministycznym językiem bezkontekstowym i wysyła deterministyczny automat do przesuwania N, który akceptuje dokładnie zaakceptowany język przez M ?$M$$L(M)$$N$$M$

Równoważne problemu byłoby skonstruować algorytm, który wprowadzany jest stosem automaty (z obietnicą L ( K ), są z góry określone, jak wyżej) i deterministycznej stosem automatów N . Wyjście byłoby tak, jeśli L ( M ) = L ( N ) i nie, jeśli L ( M ) ≠ L ( N ) .$M$$L(M)$$N$$L(M) = L(N)$$L(M)\neq L(N)$

Uważam, że algorytm rozwiązujący pierwszy dałby algorytm rozwiązujący drugi przez rozstrzygalność równoważności deterministycznych automatów wypychających. Myślę, że rozwiązanie drugiego oznaczałoby rozwiązanie pierwszego, ponieważ zliczamy wszystkie deterministyczne automaty wypychające i uruchamiamy na nich algorytm jeden po drugim, gdy tylko otrzymamy tak, wyprowadzamy ten automat.

Zastanawiam się, czy ktoś coś o tym wie? Może to znany problem i / lub znane rozwiązanie? Nawiasem mówiąc, uważam, że rozstrzygnięcie stanowi wprowadzenie ograniczenia, które mówi, że język generowany przez PDA jest słownym problemem grupy.

Weź deterministyczną TM $M$ i słowo $w$ . Rozważmy jego historie obliczeniowe dla słowa $w$ . Niech $L$ będzie niepoprawnymi historiami (te, które nie zaczynają się na $w$ , nie kończą się akceptacją lub są nieprawidłowe). Albo $L = A^{\ast}$ ( $M$ nie akceptuje $w$ ), albo $L = A^{\ast} - \{h\}$ dla niektórych ciągów $h$ ( $M$ akceptuje $w$ przy historii obliczeń $h$ ). Przede wszystkim $L$jest skuteczny CFL, w tym sensie, że możesz zbudować gramatykę / PDA, rozpoznając go. Co więcej, $L$ jest (nieefektywnym) DCFL, ale nie można skutecznie pokazać DPDA. Co więcej, $L$ jest (nieefektywny) regularny.

Małe wyjaśnienie:

Zapytałeś, czy można rozwiązać następujący problem:

biorąc pod uwagę PDA $M$ obiecał, że $L(M)$ jest DCFL, a DPDA $N$ określa, czy $L(M) = L(N)$ .

Odpowiedź brzmi „nie” i w rzeczywistości zachodzi następujący silniejszy fakt: następujący problem jest nierozstrzygalny:

biorąc pod uwagę, że PDA $M$ obiecało, że $L(M)$ jest regularne, ustal, czy $L(M)=A^{\ast}$ .