Combinaison d'automates finis déterministes

Question

Je suis vraiment novice dans ce domaine, alors je m'excuse pour la noobishness ici.

construire un Deterministic Finite Automaton DFA reconnaissant la langue suivante:

L= { w : w has at least two a's and an odd number of b's}. 

L'Automatiser pour chaque partie de ce (at least 2 a's, odd # of b's) sont faciles à faire séparément ... Quelqu'un peut-il expliquer s'il vous plaît d'une manière systématique de les combiner en un seul? Merci.

Answer 1

C'est fait en utilisant le product de deux automates.

Answer 2

La langue L où a sont au moins deux et b sont impairs est une langue régulière. Son DFA est comme ci-dessous:

Dans ce DFA j'ai combiné deux DFS s sur le plan conceptuel!

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram) 
DFA-2 = for >= two a   (placed Horizontally two times in diagram) 

_{Le DFA est trop symptomatique et simple, je crois donc pas besoin de mot comment combiner les deux DFA}

Pour dessiner ce DFA vous gardez toujours le suivi du nombre b s a été venir soit pair ou impair. States 0, 2 and 4 signifie que le nombre pair de b est arrivé. Vous pouvez donc diviser verticalement ce DFA en deux parties où les états inférieurs sont égaux à b s et états supérieurs à impair.

Aussi la chaîne est acceptée si impair b donc l'état final devrait être dans un d'état dans la partie supérieure.

non seulement le numéro de b s est condition mais a doit être au moins 2. Vous pouvez donc diviser ce DFA horizontalement en trois parties où le nombre de a s est 0 à state-0 and 1, a s sont un à state-2 and 3 et a sont 2 à state-4 and 5. Après les deux premiers a s un nombre de a sont autorisés dans la chaîne de sorte qu'il y ait auto boucle à l'état q4 et q5.

_{nombre d'état requis est six parce que, 2 état pour impair même b et que hould être atleast 2 donc trois états a = 0, a = 1, a = 2, donc 2 * 3 = 6}

Answer 3

Vous pouvez utiliser les étapes simples suivantes pour créer un DFA combiné.

Soit Σ = {a , un , ..., a _k}.
1ère étape: DFA design pour les deux langues et le nom de leur état Q , Q ...

2ème étape: Renommer tous les états dans les deux DFA unique à savoirrenommer tous les états dans DFA comme Q , Q , Q , Q ... vous avez démarré avec l'indice 0; cela signifie qu'aucun État n'aurait le même nom.

3ème étape: tableau Construct de transition (δ) à l'aide des étapes suivantes

      3a. état de départ du combiné DFA:
            Prenez état de départ des deux DFA (DFA 1 et DFA2) et les nommer comme Q _{[i, j]} où i et j sont l'indice de l'état de début de DFA1 et DFA2 respectivement; c'est-à-dire Q _i est l'état de départ de la 1ère DFA et Q _j est l'état de départ du 2ème DFA et marque Q _{[i, j]} comme état de départ du DFA combiné.

      3b. état de la carte à la fois DFA comme
                      si δ (Q _i, un _k) = Q _p1 et δ (Q _j, un _k) = Q _p2, où Q _p1 appartient à DFA1 et Q _p2 appartient à DFA2 puis   δ (Q _{[i, j]}, un _k) = Q _{[p1, p2]}

      3c. remplir la table entière pendant qu'il y a un Q _{[i, j]} restant dans la table de transition.

      3d. état final du DFA combiné:
            Pour AND cas état final serait tout Q _{[i, j]} où Q _i et Q _j sont l'état final de DFA 1 et DFA2 respectivement.
            Pour OR cas état final serait tout Q _{[i, j]} où soit Q i ou Q j est l'état final de DFA1 et DFA2.

4ème étape: Renommer tous les Q _{[i, j]} (unique) et d'en tirer DFA ce sera votre résultat.

Exemple:

L= {w: w has at least two a's and an odd number of b's}. 

Etape 1:
DFA pour un nombre impair de années b. DFA pour au moins 2 a.

Step2:
Renommez le stae de DFA1

Etape 3 (a, b, c):
table de transition sera construite comme.

Step3d:
Depuis que nous devons prendre et à la fois l'état DFA si finale serait Q _[2,4], car il contient état final des deux DFA.
Si nous devons prendre ou des deux DFA l'état final serait Q _[0,4], Q _[2,3], Q _[1,4], Q _{[2, 4]}.
La table de transition aimerait cela après l'ajout de l'état final.

Etape 4:
renommer tous unis Q _{[i, j]}
Q _[0,3] à Q
Q _{[1, 3]} à Q
Q _[0,4] à Q
Q _[2,3] à Q 4
Q _[1,4] à Q
Q _[2,4] à Q 5
Donc DFA final ressemblera à ci-dessous.