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

16

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

Thomas Klimpel
fonte
1
Observe que a equivalência dos PDAs determinísticos é decidível.
sdcvvc

Respostas:

14

É indecidível se um PDA reconhece , o conjunto de todas as strings sobre o alfabeto de entrada.Σ

Adicionado. É indecidível verificar se eu(G)=Σ 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 , LMMxpyvocêvpvocêcpumavvocêqcbv 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,uma,q,b,eu)vocêcpumavvocêcbqv(p,uma,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 iw i + 1 . A última configuração na string deve ser final, ou seja, ter um estado de parada / final.W0 0#W1R#W2#W3R#...W0 0=q0 0xxWEuWEu+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 iw i + 1 . Essa parte da string é gerada por uma gramática semelhante a uma para { x # y Rx , y { a , b } , x y } .GM WEuWEu+1{x#yRx,y{uma,b},xy}

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

Hendrik Jan
fonte
2
Existe uma prova na Seção 17.3.3 de Engenharia da computação: teoria e lógica de autômatos aplicados por Ganesh Gopalakrishnan
Pål GD
2
Σ¯