Atualmente, estou lendo o livro Introdução à Teoria da Computação (2 ou 3 Ed.), De Michael Sipser , e me deparei com uma pergunta no Capítulo 1 - Linguagens Regulares , ou seja, quando o autor está apresentando a ideia de prova do Teorema 1.49 - "A classe de idiomas regulares é fechada sob a operação estrela." usando NFA.
A abordagem sugerida é que, se tivermos um idioma normal e quisermos provar que também é regular, podemos pegar um NFA e modificá-lo para um como na imagem abaixo, que é um NFA específico que reconhece .
Ele notou:
Uma idéia (um pouco ruim) é simplesmente adicionar o estado inicial ao conjunto de estados de aceitação. Essa abordagem certamente adiciona ao idioma reconhecido, mas também pode adicionar outras strings indesejadas.
Eu desenhei o NFA "ruim" como abaixo e tentei descobrir por que isso resultará em seqüências indesejadas. No entanto, não consigo encontrar um exemplo de quando uma string indesejada é reconhecida. Por que essa idéia resultará na NFA reconhecendo seqüências indesejadas?
Alguém poderia apontar isso para mim ou me dar uma dica, ou eu não entendi o autor? Desde já, obrigado!
fonte