logo

Exemples de NFA

Exemple 1:

Concevez un NFA pour la table de transition comme indiqué ci-dessous :

État actuel 0 1
→q0 q0, q1 q0, q2
q1 q3 e
q2 q2, q3 q3
→q3 q3 q3

Solution:

Le diagramme de transition peut être dessiné en utilisant la fonction de mappage comme indiqué dans le tableau.

méthode tostring en java
Exemples de NFA

Ici,

 δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0, q2} Then, δ(q1, 0) = {q3} Then, δ(q2, 0) = {q2, q3} δ(q2, 1) = {q3} Then, δ(q3, 0) = {q3} δ(q3, 1) = {q3} 

Exemple 2 :

Concevoir un NFA avec ∑ = {0, 1} accepte toutes les chaînes se terminant par 01.

Solution:

Exemples de NFA

Par conséquent, NFA serait :

Exemples de NFA

Exemple 3 :

Concevez un NFA avec ∑ = {0, 1} dans lequel le double « 1 » est suivi du double « 0 ».

Solution:

Le FA avec double 1 est le suivant :

Exemples de NFA

Il doit être immédiatement suivi du double 0.

Alors,

Exemples de NFA

Maintenant, avant le double 1, il peut y avoir n'importe quelle chaîne de 0 et 1. De même, après le double 0, il peut y avoir n'importe quelle chaîne de 0 et 1.

La NFA devient donc :

Exemples de NFA

Considérons maintenant la chaîne 01100011

 q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4 

Exemple 4 :

Concevez un NFA dans lequel toute la chaîne contient une sous-chaîne 1110.

Solution:

Le langage est constitué de toute la chaîne contenant la sous-chaîne 1010. Le diagramme de transition partiel peut être :

Exemples de NFA

Maintenant, 1010 pourrait être la sous-chaîne. Nous ajouterons donc les entrées 0 et 1 afin que la sous-chaîne 1010 du langage puisse être conservée. La NFA devient donc :

Exemples de NFA

La table de transition pour le diagramme de transition ci-dessus peut être donnée ci-dessous :

État actuel 0 1
→q1 q1 q1, q2
q2 q3
q3 q4
q4 q5
*q5 q5 q5

Considérons une chaîne 111010,

 δ(q1, 111010) = δ(q1, 1100) = δ(q1, 100) = δ(q2, 00) 

Est resté coincé! Comme il n'y a pas de chemin depuis q2 pour le symbole d'entrée 0. Nous pouvons traiter la chaîne 111010 d'une autre manière.

 δ(q1, 111010) = δ(q2, 1100) = δ(q3, 100) = δ(q4, 00) = δ(q5, 0) = δ(q5, ε) 

Comme l'état q5 est l'état d'acceptation. Nous obtenons le scan complet et nous arrivons à l’état final.

Exemple 5 :

Concevoir un NFA avec ∑ = {0, 1} accepte toutes les chaînes dans lesquelles le troisième symbole à partir de l'extrémité droite est toujours 0.

Solution:

Exemples de NFA

Ainsi, nous obtenons toujours le troisième symbole à partir de l’extrémité droite sous la forme « 0 ». Le NFA peut être :

Exemples de NFA

L'image ci-dessus est une NFA car dans l'état q0 avec l'entrée 0, on peut soit passer à l'état q0, soit à q1.