Je lis actuellement le livre Introduction à la théorie du calcul (2e ou 3e éd.) De Michael Sipser , et je suis tombé sur une question du chapitre 1 - Langues régulières , à savoir lorsque l'auteur présente l'idée de preuve du théorème 1.49 - "La classe des langues régulières est fermée sous l'opération étoile." en utilisant NFA.
L'approche suggérée est que, si nous avons un langage régulier et que nous voulons prouver que est également régulier, nous pouvons prendre un NFA et le modifier en comme dans l'image ci-dessous, qui est alors un NFA particulier reconnaissant .
Il a noté:
Une idée (légèrement mauvaise) consiste simplement à ajouter l'état de départ à l'ensemble des états d'acceptation. Cette approche ajoute certainement au langage reconnu, mais elle peut également ajouter d'autres chaînes indésirables.
J'ai dessiné le "mauvais" NFA comme ci-dessous et j'ai essayé de comprendre pourquoi cela entraînerait des chaînes indésirables. Cependant, je ne peux pas trouver un exemple de quand une chaîne indésirable est reconnue. Pourquoi cette idée entraînera-t-elle la NFA à reconnaître les chaînes indésirables?
Quelqu'un pourrait-il me le signaler ou me donner un indice, ou ai-je mal compris l'auteur? Merci d'avance!
la source