Na descrição formal do determinística Pushdown Automata, eles permitem movimentos, onde a máquina pode pop ou empurrar símbolos na pilha sem ler um símbolo da entrada. Se esses ϵ movimentos não forem permitidos, e a pilha puder ser modificada apenas uma vez após a leitura de cada símbolo, os autômatos resultantes são iguais à energia dos DPDAs?
Talvez esteja faltando algo trivial no que diz respeito ao uso do conjunto de potências de como seu novo Γ , permitindo que você "comprima" ϵ move-se para o autômato equivalente sem eles, semelhante a como você pode comprimir ϵ em um DFA. Parece que essa conversão não é tão trivial quanto para os DFAs e não tenho certeza de que seja possível.
Então, os dois são equivalentes em poder? Eu só estou perguntando porque toda a gente parece supor que DPDAs têm movimentos e eu estou querendo saber por que existe essa hipótese, uma vez que parece ser um modelo mais complexo.
fonte
Respostas:
Talvez eu tenha encontrado alguma informação relevante em:
Jean-Michel Autebert, Jean Berstel, Luc Boasson; Linguagens sem contexto e autômatos de empilhamento; Manual de Línguas Formais; 1997, pp 111-174
Os DPDAs sem transições são conhecidos como autômatos determinísticos em tempo realϵ .
Eles são menos poderosos que os DPDAs, por exemplo
é determinístico e pode ser reconhecido por um DPDA, mas não pode ser reconhecido por nenhum tempo real DPDA em .
O que você pode fazer é eliminar aumentando -transitions:ϵ
Proposição 5,4 : Para qualquer DPDA é possível construir um DPDA reconhecer a mesma língua de tal modo que qualquer -rule está a diminuir.ϵ
fonte