Quelqu'un peut-il m'expliquer en détail comment dessiner un diagramme de transition (DFA/NFA) en théorie de l'informatique?

Question

Ok donc ce sujet est un peu déroutant. Je peux très bien comprendre la table de transition, mais en ce qui concerne le diagramme, j'ai du mal à savoir sur quelle base le diagramme est créé. Quelqu'un peut-il m'expliquer en détail sur quelle base nous devons construire un diagramme de transition de Dfa et Nfa.

Answer 1

Vous devez simplement effectuer des conditions de type if-elseif pour dessiner le DFA à partir de la table. I.e Automates déterministes finis dans lesquels la décision pour toute entrée doit être déterministe, c'est-à-dire qu'il devrait y avoir une confirmation de sortie sur une entrée particulière. Il n'a donc qu'un seul état en sortie pour une entrée particulière.

NFA: i.e. non déterministes automates finis dans lesquels la décision pour toute entrée peut ne pas être déterministe-à-dire il ne peut y avoir confirmation de la sortie sur l'entrée particulière. Il peut donc avoir un ou plusieurs états en sortie pour une entrée particulière.

• Prenons un exemple pour la construction de diagramme DFA:

Supposons que vous ayez table de transition donnée comme:

Le → indique l'état initial: ici q0

Le signe * indique l'état final (ici un seul état final q1)

Le diagramme DFA pour cette table serait:

Explication:

• A partir du tableau, il est clair que de l'état de départ à savoir A, quand vous obtenez le symbole 0 en entrée, vous devez passer à l'état C, et lorsque vous obtenez le symbole 1 en entrée, vous devez passer à l'état B.

  n diagramme, nous montrons des flèches entre deux états selon le symbole. Comme ceci, nous passons à B, et le tableau montre que sur le symbole 0 en entrée, allez à l'état C et sur le symbole 1 en entrée, allez à l'état B. Donc vous dessinez deux flèches selon ceci. A partir de C, sur le symbole 0 en entrée, passer à l'état C, et sur le symbole 1 en entrée, passer à l'état D, c'est-à-dire à l'état final. Donc vous dessinez deux flèches pour cela.

• Encore une fois le même processus est fait pour D.

REMARQUE: Pour montrer un état comme état initial, vous ajoutez une flèche derrière le cercle indiquant le premier état, et pour désigner l'état comme état final, vous dessinez un cercle à l'intérieur d'autres comme le montre la figure.

• Prenons un autre exemple pour la construction de diagramme NFA:

Supposons que vous ayez table de transition donnée comme:

Le diagramme NFA pour la table peut être construit comme:

Vous pouvez facilement comprendre le concept, car le concept est le même que la construction de diagramme DFA. La différence ici serait que, sur une seule entrée, il peut y avoir plusieurs états de sortie; Vous devez donc dessiner une flèche pour chacun des états de sortie.

DFA pour les chaînes qui commence par 0 et se termine par 1:

Construction:

1. dessiner un cercle d'état initial 1.

2. Comme la chaîne devrait commencer par 0, donc, sur en obtenant un 0 comme entrée, la transition devrait aller de l'avant avec l'état suivant 2 car notre premier cas est satisfaisant ici. Donc, faites un nouveau cercle d'état 2 et montrez 0 comme entrée sur la flèche entre les deux états.

   Mais le problème est, quand vous obtenez l'entrée 1, alors vos deux cas (0 devrait être la première entrée et 1 devrait être la dernière) ne peuvent jamais être satisfaits maintenant. Donc pour cela faites un autre cercle d'état 3 pour l'entrée 1, et montrez une flèche à cet état qui va au même état 3 sur l'entrée 1 et 0. Comme vos conditions ne peuvent jamais être satisfaites maintenant, donc vous laissez votre état 3 ici en montrant une boucle à lui-même. Maintenant, passons à l'état 2. Lorsque vous entrez 0, vous devez montrer la boucle à l'état 2 lui-même, car votre condition finale "1 devrait être à la fin de la chaîne" est ne pas satisfaire en obtenant un 0 comme entrée -> donc vous ne pouvez pas passer à l'état final pour cela. Mais quand vous obtenez l'entrée 1 sur l'état 2, alors vous obtenez vos deux conditions (0 devrait être la première entrée et 1 devrait être la dernière), sont satisfaisantes. Donc, vous faites la flèche à l'état final-4 pour l'entrée 1 sur l'état-2. Maintenant, sur l'état final, c'est-à-dire l'état-4, vous pouvez toujours obtenir une entrée car il n'y a pas de longueur donnée de la chaîne. Ainsi, vous pouvez toujours obtenir les entrées 1 et 0.

   • Lorsque vous obtenez l'entrée en 1 sur l'état final, votre chaîne serait maintenant quelque chose comme 011 de sorte que votre fois la condition est satisfaisant maintenant, vous faites une boucle à l'état final sur l'entrée 1.Mais quand vous obtenez l'entrée comme 0 sur l'état final, c'est-à-dire l'état-4 alors votre chaîne serait quelque chose comme 010 alors votre seule condition "1 devrait être le dernier élément de la chaîne" n'est pas satisfaisante alors vous faites un passage de l'état 4 à l'état 3 car c'est le seul état qui peut résoudre le problème de l'obtention de 1 à la fin de la chaîne.

espère que vous comprenez le concept maintenant et vous aider!

Answer 2

Le diagramme est une représentation alternative sous forme de graphique. Le diagramme contient chaque état en tant que nœud et chaque transition d'état en tant qu'arrêt. Disons que vous avez deux états A et B et une transition (A, x, B). Le graphe correspondant a deux noeuds A et B et un bord de A à B avec l'étiquette x sur le bord. Les états de début et de fin ont des signes spéciaux dans le graphique pour pouvoir les reconnaître.