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 :
