É decidível se um autômato de pushdown reconhece um determinado idioma regular?

O problema de dois autômatos de pushdown reconhecerem o mesmo idioma é indecidível. O problema de decidir se um autômato de empilhamento reconhece o idioma vazio é decidível; portanto, também é decidível se ele reconhece um determinado idioma finito. É indecidível se o idioma aceito por um autômato de empilhamento é regular. Mas ...

... é decidível se um autômato de pushdown reconhece um determinado idioma regular?

Caso a resposta seja não, o problema se tornará decidível se o idioma regular fornecido tiver a altura estrela ?$1$

É indecidível se um PDA reconhece , o conjunto de todas as strings sobre o alfabeto de entrada.$\Sigma^*$

Adicionado. É indecidível verificar se $L(G)=\Sigma^*$ como conseqüência do fato de que cálculos "não válidos" de uma TM podem ser codificados como strings de um CFG. Este é o Lema 8.7 da Introdução à Teoria dos Autômatos, de Hopcroft e Ullman. Os autores referem-se a este resultado em Hartmanis (1967), Linguagens sem contexto e cálculos de máquinas de Turing.

Uma codificação conveniente dos cálculos de uma máquina de Turing é a seguinte. Uma configuração do TM M é uma sequência da forma x p y em que u v é o conteúdo da fita e o estado p é indicado na posição em que a cabeça reside. É importante observar que as etapas computacionais de uma TM são alterações locais : u c p a v ⊢ u q c b v para a instrução ( p , a , q , b , $M$$M$$xpy$$uv$$p$$ucpav \vdash uqcbv$ Em que a cabeça se move para a esquerda, e u c p um v ⊢ u c b q v para a instrução ( p , um , q , b , R ) em que a cabeça se move para a direita.$(p,a,q,b,L)$$ucpav \vdash ucbqv$$(p,a,q,b,R)$

Uma computação válida pode ser codificada como uma string onde w 0 = q 0 x codifica a configuração inicial na string x , e temos as etapas adequadas w i ⊢ w i + 1 . A última configuração na string deve ser final, ou seja, ter um estado de parada / final.$w_0\#w_1^R\#w_2\#w_3^R\# \dots$$w_0 = q_0x$$x$$w_i \vdash w_{i+1}$

Agora é um exercício para verificar se as seqüências que não são computações válidas podem ser geradas por um CFG (ou aceito por um PDA). As strings que não consistem em sequências de configuração são regulares. Caso contrário, um não-deterministamente supõe uma posição onde não w i ⊢ w i + 1 . Essa parte da string é gerada por uma gramática semelhante a uma para { 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\}$

Se o TM não tem cordas aceito, ele não terá cálculos válidos, e todas as cordas são gerados pela gramática G M .$M$$G_M$