Czy jest rozstrzygalne, czy automat przesuwający rozpoznaje dany regularny język?

Problem, czy dwa automaty przesuwające rozpoznają ten sam język, jest nierozstrzygalny. Problem, czy automat przesuwający rozpoznaje pusty język, jest rozstrzygalny, a zatem decydujące jest, czy rozpoznaje dany język skończony. Nie można rozstrzygnąć, czy język akceptowany przez automat pushdown jest regularny. Ale ...

... czy można zadecydować, czy automat przesuwający rozpoznaje dany regularny język?

W przypadku odpowiedzi przeczącej, czy problem staje się rozstrzygalny, jeśli dany język regularny ma wysokość gwiazdy $1$ ?

Nie można rozstrzygnąć, czy PDA rozpozna , zestaw wszystkich ciągów znaków na alfabecie wejściowym.$\Sigma^*$

Dodany. Nie można rozstrzygnąć, czy jest konsekwencją faktu, że „nieważne” obliczenia TM mogą być kodowane jako ciągi CFG. To jest Lemma 8.7 z Wstępu do teorii automatów autorstwa Hopcroft i Ullman. Autorzy odnoszą się do tego wyniku do Hartmanisa (1967), Języki bezkontekstowe i obliczenia maszynowe Turinga.$L(G)=\Sigma^*$

Wygodne kodowanie obliczeń maszyny Turinga jest następujące. Konfiguracja TM M jest ciągiem Formie x p y , gdzie u , v jest zawartość w taśmie, a stan P jest widoczny na przebywa głowicy obiektu na pozycji gdzie. Należy zauważyć, że kroki obliczeniowe TM są lokalnymi zmianami: u c p a v ⊢ u q c b v dla instrukcji ( p , a ), w której głowa porusza się w lewo, i u $M$$M$$xpy$$uv$$p$$ucpav \vdash uqcbv$$(p,a,q,b,L)$ dla instrukcji ( p , a , q , b , R ), gdzie głowa porusza się w prawo.$ucpav \vdash ucbqv$$(p,a,q,b,R)$

Prawidłowe obliczenia można zakodować jako ciąg gdzie w 0 = q 0 x koduje początkową konfigurację ciągu x , a my mamy odpowiednie kroki w i ⊢ w i + 1 . Ostatnia konfiguracja w ciągu powinna być ostateczna, tzn. Mieć stan zatrzymania / końcowy.$w_0\#w_1^R\#w_2\#w_3^R\# \dots$$w_0 = q_0x$$x$$w_i \vdash w_{i+1}$

Jest to teraz ćwiczenie sprawdzające, czy ciągi, które nie są prawidłowymi obliczeniami, mogą być generowane przez CFG (lub akceptowane przez PDA). Ciągi, które nie składają się z sekwencji konfiguracji, są nawet regularne. W przeciwnym razie jeden niedeterministycznie zgaduje pozycję, w której nie w i ⊢ w i + 1 . Ta część łańcucha jest generowana przez gramatykę podobną do gramatyki { x # y R ∣ x , y ∈ { a , b } ∗ , x ≠ y } .$G_M$ $w_i \vdash w_{i+1}$$\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$

$M$$G_M$ .