# Deterministic finite state machine Excercise solutions

Let us see the Deterministic finite state machine Exercises solutions. In this tutorial, we will draw a DFA for the Regular Expression of (a+b)*b+(bb)*a.

## Explanation of Strings of the langugage

• 2 Accepted strings of length 1 = {b,a no more possible string}
• 2 Accepted strings of length 2 = {ab , bb, â€¦ and many more similar strings }
• 2 Accepted strings of length 5 = {aaabb, bbbba,… and many more similar strings}
• 2 Accepted strings of length 8 = {aabbabab, bababbab, â€¦ and many more similar strings }
• 2 Accepted strings of length 10 = {aaaaababab , ababababab , â€¦ and many more similar strings }
• 2 Accepted strings of length 15 = { aaaaabbaababaab, bbbbbbbbbbbbbba , â€¦ and many more similar strings }
• 2 Accepted strings of length 20 = { aaaabbbbbbababababbb , abbbbbaaaabbabbaabab , â€¦ and many more similar strings }
• 2 Accepted strings of length 25 = { aaaaaaaaaabbbbbbaaaaaaaab , bbbbbbbbbbbbbbbbbbbbbbbba , â€¦ and many more similar strings }
• and many more similar strings

0 to 3

0 to 1

0 to 1 |Â  0 to 3

0 to 3 | 3 to 4

0 to 1 |1 to 2 |2 Â to 2 | 2 to 1 | 1 to 1 |

0 to 3 |3Â  to 4Â  | 4 to 3 | 3Â  to 4 | 4Â  to 1 Â |

0 to 1 | 1to 2 | 2 to 1 | 1Â  to 1 | 1 to 2 | 2Â  to 1 | 1Â  to 2 | 2 to 1 |

0Â  to 3Â  | 3 to 2Â  | 2 toÂ  1| 1 to 2 | 2 to 1 |Â  1 to 1 | 1 to 2 | 2 to 1 |

0Â  to 1Â  | 1 to 2Â  | 2 toÂ  2| 2 to 2 | 2 to 2 |Â  2 to 1 | 1 to 2 | 2 to 1 |1Â  to 2Â  | 2 to 1Â  |

0Â  to 1Â  | 1 to 1Â  | 1 toÂ  2| 2 to 1 | 1 to 2 |Â  2 to 1 | 1 to 2 | 2 to 1 |1Â  to 2Â  | 2 to 1Â  |

0Â  to 1Â  | 1 to 2| 2 to Â 2| 2 to 2 | 2 to 2 |Â  2 to 1 | 1 to 1 | 1 to 2 |2Â  to 2Â  | 2 to 1Â  | 1 to 2 | 2 to 1 | 1 to 2 |2Â  to 2Â  | 2 to 1Â  |

0Â  to 3Â  | 3 to 4Â  | 4 toÂ  3| 3 to 4 | 4 to 3 |Â  3 to 4 | 4 to 3 | 3 to 4 |4Â  to 3Â  | 3 to 4 |4 to 3Â  | 3 toÂ  4| 4 to 3 | 3 to 4 |Â  4 to 1 |

0Â  to 1Â  | 1 to 2Â  | 2 toÂ  2| 2 to 2 | 2 to 1 |1 to 1Â  | 1 toÂ  1| 1 to 1 | 1 to 1 |Â  1 to 1 | 1 to 2 | 2 to 1 |1Â  to 2Â  | 2 to 1 |1Â  to 2Â  | 2 to 1 |1Â  to 2Â  | 2 to 1 | 1 to 1 |Â  1 to 1 |

0Â  to 1Â  | 1 to 1Â  | 1 toÂ  1| 1 to 1 | 1 to 1 |Â  1 to 1 | 1 to 2 | 2 to 2 |2Â  to 2Â  | 2 to 2Â  |2 to 1Â  | 1 toÂ  1| 1 to 2 | 2 to 1 |Â  1 to 1 | 1 to 2 | 2 to 2 |2Â  to 1Â  | 1 to 2Â  |2 to 1Â  |

0to 1 | 1 to 2Â  | 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 1| 1 toÂ  1| 1 to 1 | 1 to 1 |Â  1 to 1 | 1 to 1 | 1 to 2 | 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 2| 2 to 1|

0Â  to 3Â  | 3 to 4Â  | 4 toÂ  3| 3 to 4 | 4 to 3 |Â  3 to 4 | 4 to 3 | 3 to 4 |4Â  to 3Â  | 3 to 4 |4 to 3Â  | 3 toÂ  4| 4 to 3 | 3 to 4 Â |4 to 3Â  | 3 toÂ  4| 4 to 3 | 3 to 4 Â |4 to 3Â  | 3 toÂ  4| 4 to 3 | 3 to 4 Â | 4 to 3| 3 to 4 | 4 to 1 |

## Finite Automata Exercise Solution

Here I am showing you a list of some more important Deterministic Finite Automata used in the theory of automata and theory of computation.

1. DFA forÂ Â (a+b)* (a+b)aÂ .
2. DFA forÂ (bb)*(aa)*Â .
3. DFA forÂ Â b+a(a+b)*+a.
4. DFA forÂ (a+b)*b+(bb)*a.
5. DFA forÂ bb+a(a+b)*+aa.
6. DFA forÂ Â a(a+b)*+bb(a)*Â .
7. DFA forÂ Â a(a+b)b*+bb(a)*.
8. DFA forÂ Â b(aa)*a+a(bb)*b.
9. DFA forÂ a+a(aa+b)*(aa)b.
10. DFA forÂ a+a(aa+b)*+(aa)b.
11. DFA forÂ (a+b)b(a+b)*+(aa)*b.
12. FA for stringsÂ starting with a and ending with a.
13. FA for the language of all those stringsÂ starting with a.
14. FA for the language of all those strings containingÂ aa as a substring.
15. DFA for the language of all those stringsÂ starting and ending with the same letters.
16. DFA for the language of all those stringsÂ starting and ending with different letters.
17. DFA for the language of all those stringsÂ having double 0 or double 1.
18. DFA for the language of all those stringsÂ starting and ending with b.
19. DFA forÂ ending with b.
20. DFA for the string ofÂ even Aâ€™s and even bâ€™s.
21. DFA for the regular expression ofÂ Â a(a+b)*+(bb)+a(ba)*+aba+bb*(a+b)*.
22. RegExp and DFA for strings havingÂ triple aâ€™s or triple bâ€™s.