é possível minimizar os autômatos de empilhamento?

8

é possível minimizar os autômatos de empilhamento? Se não, por quê? É porque, para minimização, as classes de equivalência precisam ter um índice finito e não podemos garantir isso para o CFG?

computability automata pushdown-automata Tom J.
fonte

Respostas:

8

Infelizmente, o problema não é computável. É indecidível até dizer se dois PDAs arbitrários são equivalentes; minimizar um PDA é ainda mais difícil.

DW
fonte
6

Eu respondi basicamente a mesma pergunta (coloque de maneira mais geral) aqui .

O argumento em resumo: se você pudesse fazer isso, poderia decidir a universalidade e algumas outras propriedades indecidíveis do PDA / CFG. Portanto, por redução, não pode haver esse minimizador.

Rafael
fonte
4

Desculpe, minimizar em termos de quê?

Todo PDA tem um equivalente com um único estado.

Hendrik Jan
fonte
É verdade. :) Eu acho que "tamanho de uma codificação razoável", por exemplo, a tabela de transição. As outras respostas funcionariam com isso, não?
Raphael
2

Não sei como minimizar a maneira como você faz com autômatos que não são de empilhamento, mas ...

Você pode converter um CFG para PDA, certo? E essa conversão, segundo Hopcroft, tem apenas um estado, que é muito minimizado, você não acha? Então, tudo o que você precisa fazer é converter seu PDA em CFG e, em seguida, seu CFG novamente em PDA, você terá um PDA de 1 estado.

H_DANILO
fonte
Observe que isso é mínimo de estado, mas não mínimo de transição. Como a DW diz, tornar a transição e o estado mínimo é incontestável.
jmite
0

"minimizar" normalmente significa "mínimo global", mas às vezes pode se referir a um "mínimo local"; nesse caso, existem heurísticas, ou seja, estratégias que podem resultar em alguma redução, mas não encontrar consistentemente o mínimo global. e também algumas classes especiais de PDAs podem ser minimizadas ou "aparadas". Algoritmos de otimização de aprendizado de máquina com "terminação não garantida", por exemplo, algoritmos genéticos também podem ser empregados aqui. Aqui estão dois artigos sobre "visivelmente empurrar para baixo autômatos" de uma subclasse. 2 documentos de exemplo ao longo destas linhas:

vzn
fonte