Um idioma pode ter mais de um DFA?

17

Por exemplo, quando consideramos um DFA que permite que as seqüências de caracteres não tenham sub-sequências 00ou 11eu possa produzir os dois DFAs a seguir:

insira a descrição da imagem aqui

automata finite-automata Madhuri
fonte

Respostas:

37

Primeiro, o DFA esquerdo está incorreto - ele aceita, por exemplo, 011.

Em segundo lugar, os DFAs podem ser minimizados canonicamente ; portanto, nesse sentido, você sempre pode encontrar um DFA canônico para um determinado idioma.

Mas, em geral, existem infinitamente muitos DFAs diferentes para cada idioma, para que você possa obter respostas corretas diferentes.

Shaull
fonte
E isso é infinitamente até o isomorfismo.
G. Bach
N
Infinitamente muitos DFAs diferentes, mesmo para idiomas finitos?
Bergi
1
@ Bergi: Certamente - você pode adicionar quantos estados redundantes quiser. Isso pode parecer "bobo", e é realmente sem sentido quando você mesmo constrói um autômato. No entanto, muitas vezes os autômatos são construídos através da tradução de algum outro formalismo (por exemplo, determinação de NFAs); nesse caso, é muito provável que você obtenha estados redundantes.
Shaull
@ Shaull: Você quer dizer com transições ε ou estados inacessíveis? OK, eu não considerei isso.
Bergi