Exemple 1:

Concevoir un FA avec ∑ = {0, 1} accepte les chaînes qui commencent par 1 et se terminent par 0.

Solution:

Le FA aura un état de départ q0 à partir duquel seul le front avec l’entrée 1 passera à l’état suivant.

Dans l'état q1, si on lit 1, on sera dans l'état q1, mais si on lit 0 à l'état q1, on arrivera à l'état q2 qui est l'état final. Dans l'état q2, si nous lisons 0 ou 1, nous passerons respectivement à l'état q2 ou à l'état q1. Notez que si l'entrée se termine par 0, elle sera dans l'état final.

exemples de DFA

Exemple 2 :

Concevoir un FA avec ∑ = {0, 1} accepte la seule entrée 101.

Solution:

Dans la solution donnée, nous pouvons voir que seule l’entrée 101 sera acceptée. Par conséquent, pour l’entrée 101, aucun autre chemin n’est affiché pour une autre entrée.

Exemple 3 :

La conception FA avec ∑ = {0, 1} accepte un nombre pair de 0 et un nombre pair de 1.

Solution:

recherche linéaire en java

Cette FA considérera quatre étapes différentes pour l’entrée 0 et l’entrée 1. Les étapes pourraient être :

Ici, q0 est un état de départ et également l’état final. Notez soigneusement qu'une symétrie des 0 et des 1 est maintenue. Nous pouvons associer des significations à chaque état comme suit :

q0 : état d'un nombre pair de 0 et d'un nombre pair de 1.
q1 : état du nombre impair de 0 et du nombre pair de 1.
q2 : état du nombre impair de 0 et du nombre impair de 1.
q3 : état du nombre pair de 0 et du nombre impair de 1.

Exemple 4 :

La conception FA avec ∑ = {0, 1} accepte l'ensemble de toutes les chaînes avec trois 0 consécutifs.

télécharger des vidéos YouTube avec VLC

Solution:

Les chaînes qui seront générées pour ces langues particulières sont 000, 0001, 1000, 10001, .... dans lesquelles 0 apparaît toujours dans un groupe de 3. Le graphe de transition est le suivant :

Notez que la séquence de triples zéros est maintenue pour atteindre l’état final.

Exemple 5 :

Concevoir un DFA L(M) = {w | w ε {0, 1}*} et W est une chaîne qui ne contient pas de 1 consécutifs.

10 à la puissance 6

Solution:

Lorsque trois 1 consécutifs apparaissent, le DFA sera :

Ici, deux 1 consécutifs ou un seul 1 sont acceptables, donc

Les étapes q0, q1, q2 sont les états finaux. Le DFA générera les chaînes qui ne contiennent pas de 1 consécutifs comme 10, 110, 101,..... etc.

Exemple 6 :

Concevoir un FA avec ∑ = {0, 1} accepte les chaînes avec un nombre pair de 0 suivis d'un simple 1.

Solution:

Le DFA peut être représenté par un diagramme de transition comme :