Réduire un DFA à un NFA

Question

J'essaye de comprendre un problème où je dois dessiner un NFA pour une langue donnée.

La langue est { w | the final five symbols of w include two a's and three b's }. Je crois que je l'ai comme un DFA et je ne suis pas sûr s'il y a une version plus réduite. Si quelqu'un pouvait jeter un coup d'œil, ce serait très utile. Je me sens comme si elle pouvait être réduite à une NFA assez petite.

Answer 1

Tout d'abord, ce que vous avez il n'y a pas DFA; état a est clairement non déterministes:

• avec un a vous pouvez aller à la fois a et b
• avec un b vous pouvez rejoindre à la fois a et s

En second lieu, puisque dans un FSA vous ne peut compter qu'avec les états (il n'y a pas de pile), vous devez garder une trace du nombre de chaque symbole que vous avez vu dans les 5 derniers caractères de l'espace d'état. Pensez simplement au nombre de combinaisons différentes dont vous avez besoin, puis les transitions seront évidentes. C'est la plus petite NFA avec laquelle vous pouvez résoudre cet exercice.