Actualmente estoy leyendo el libro Introducción a la teoría de la computación (2da o 3ra ed.) De Michael Sipser , y me he topado con una pregunta en el Capítulo 1 - Lenguajes regulares , es decir, cuando el autor presenta la idea de prueba del Teorema 1.49 - "La clase de idiomas regulares está cerrada bajo la operación estrella". usando NFA.
El enfoque sugerido es que, si tenemos un lenguaje regular y quiero demostrar que también es regular, podemos tomar un NFA y modificarlo en un como en la imagen a continuación, que es entonces un NFA particular que reconoce .
El lo notó:
Una idea (ligeramente mala) es simplemente agregar el estado de inicio al conjunto de estados de aceptación. Este enfoque ciertamente agrega al lenguaje reconocido, pero también puede agregar otras cadenas no deseadas.
Dibujé el NFA "malo" como se muestra a continuación y traté de averiguar por qué esto dará como resultado cadenas no deseadas. Sin embargo, no puedo encontrar un ejemplo de cuándo se reconoce una cadena no deseada. ¿Por qué esta idea dará como resultado que la NFA reconozca cadenas no deseadas?
¿Podría alguien señalarme esto o darme una pista o no he entendido bien al autor? ¡Gracias por adelantado!
fuente