Trouver le complément d'un DFA?

Comme vous l'avez dit dans la question:

Je sais que pour convertir un DFA, M pour le compléter, M`, j'ai juste besoin de swap initial d'accepter les états et finale d'accepter les états.

Son pas complétermais vous faites quelque chose comme inverse d'une langue et langages réguliers sont de fermeture en vertu de l'inversion.

Renversement de DFA

Qu'est-ce que le Renversement de la Langue ?

La reprise d'une langue L (notée L^R) est le langage composé de
le renversement de toutes les chaînes dans L.

Étant donné que L est L(A) pour certains, FA A, on peut construire un automate pour L^R:

• inverse de tous les bords (les arcs) dans la transition diagramme

• de l'acceptation de l'état de la L^R automate est l'état de départ pour Un

• créer un nouvel état de départ pour le nouvel automate avec epsilon-transitions à chacun de l'accepter unis pour Un

Note: En renversant tous ses flèches et d'échanger les rôles de la formation initiale et l'acceptation des etats de DFA que vous pouvez obtenir un ADN à la place.

_{c'est pourquoi j'ai écrit FA(pas DFA)}

Compléter DFA

Trouver le complément d'un DFA?

Defination: Le complément d'une langue est définie en termes de différence de Σ* (sigma star). c'est L^' = Σ^* - L.

Et le complément de la langue (L^') de L a toutes les chaînes de Σ* (sigma star) à l'exception des chaînes de L. Σ* tout est possible chaînes sur l'alphabet Σ.

_{Σ = Ensemble de symboles de langue}

Pour construire les DFA D qui accepte le complément de L, il suffit de convertir
chaque état qui a accepté la dans Une dans une non-acceptation de l'état en D et les convertir
chaque non-acceptation de l'état dans Un dans un accepter de l'état dans D.

(Avertissement! Ce n'est pas vrai pour la NFA est)

_{est DFA de L, D est pour compléter}

Note: construire compléter les DFA, ancien DFA doit être complète signifie qu'il devrait tout est possible, va au bord de chaque état(ou en d'autres termes δ doit être une fonction complète).

Complément: référence à l'exemple

Compléter DFA pour Expression Régulière (00+1)*

ci-dessous est DFA nommé Un:

Mais pas cette DFA n'est pas complète DFA. la transition de la fonction δ est partiellement défini, mais pas pour le domaine complet Q×Σ (manquant, va au bord de t1 pour lable 1).

Sa DFA peut être comme suit (Un):

Ci-dessus DFA, toutes les transactions sont définies (*pour chaque paire de Q,Σ *) et δ est une fonction complète dans ce cas.

Reff: apprendre ce qu'est une Fonction Partielle.

En complément du DFA D peut être construit en changeant tous les états finaux q0 de ne pas les états finaux et vice-versa.

Donc en complément q0 devenir non-final et q1, q2 sont les états finaux.

Maintenant, vous pouvez écrire une expression Régulière pour compléter la langue à l'aide de ARDEN THÉORÈME et DFA j'ai donné.

Ici, je suis en train d'écrire une Expression Régulière pour compléter directement:

(00 + 1)* 0 (^ + 1(1 + 0)*)

où ^ est null symbole.

quelques liens utiles:

De ici et par le biais de mon profil, vous pouvez en trouver d'autres réponses utiles sur FA. Aussi, deux bons liens sur les propriétés de langage régulier: un, deuxième