Je suis en train de résoudre DFA

Question

Je dois faire L1 U L2 et intersection L1 n L2

Answer 1

Vous pouvez exécuter à travers la construction de la machine de produit cartésien formel pour dériver algorithmiquement automates pour l'intersection et l'union de L1 et L2. Cependant, étant donné que ces langages sont si faciles, il peut être plus simple de donner les langues et de simplement écrire un DFA pour chacun d'eux. L1 est le langage de toutes les chaînes de as et bs avec au moins un a. L2 est le langage de toutes les chaînes de as et bs avec au moins deux bs.

Pour accepter l'intersection de L1 et L2, nous devons voir au moins un as et deux bs. Ci-dessous, nous avons six états:

1. q0, l'état initial, où nous avons besoin d'un un et deux bs
2. q1, où nous avons encore besoin de deux bs
3. q2, où nous avons encore besoin d'un b
4. q3, où nous avons besoin de plus (Etat acceptant)
5. q4, où nous avons encore besoin d'un a et un b

6. q5, où nous avons encore besoin d'un un

   ---> q0-a-> q1-b-> q2-b-> q3 -b-> q4-a-> q3 q2 -b-> q5-a-> q3

(où les transitions sont manquantes, elles sont auto-boucles)

Notez qu'il existe six états: c'est la même chose que si nous avions effectué la construction de la machine cartésienne sur les DFA d'origine de deux et trois états, respectivement. Pour l'union, nous pouvons utiliser exactement le même DFA et changer l'ensemble des états acceptants en q1, q3, q5. Ceci capture le fait que nous acceptons maintenant quand l'une ou l'autre condition est vraie (et les états q1 et q5 sont où un, mais pas les deux (comme dans q3) sont satisfaits).