Finite Automata Theory Excercise Solutions – TAFL

By: Prof. Dr. Fazal Rehman | Last updated: December 28, 2023

Strings of DFA

• 2 Accepted strings of length 1={a}
• 2 Accepted strings of length 2={No Strings}
• 2 Accepted strings of length 5={ abaab, No more strings}
• 2 Accepted strings of length 8={aaaaaaab, abbbbaab, many more strings}
• 2 Accepted strings of length 10={aaaaaaaaab, abbbbbbaab, many more strings}
• 2 Accepted strings of length 15={aaaaaaaaaaabaab,abbbbbbbbbbbaab, many more strings}
• 2 Accepted strings of length 20={aaaaaaaaaaaaaaaaaaab,abbbbbbbbbbbbbbbbaab, More strings}
• 2 Accepted strings of length 25={aaaaaaabaaaaaaaaaaaaaaaab,abbbbbbbbbbbbbbbbbbbbbaab, many more strings}

How to read strings from FA?

How to read a?

0 to 4

How to read abaab?
0 to 4 | 4 to 1 | 1 to 2 | 2 to 3 | 3 to 4

How to read aaaaaaab?

0 to 4 | 4 to 2 | 2 to 3  | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 4

How to read abbbbaab?

0 to 4 | 4 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 2 | 2 to 3 | 3 to 4

How to read aaaaaaaaab?

0 to 4 | 4 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 4

How to read aaaaaaaaaaabaab?

0 to 4 | 4 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 4

| 4 to 2 | 2 to 3 | 3 to 4

How to read abbbbbbbbbbbaab?

0 to 4 | 4 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 1 | 1 to 2 | 2 to 3 | 3 to 4

How to read aaaaaaaaaaaaaaaaaaab?

0 to 4 | 4 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 |3 to 2 | 2 to 3 |3 to 2 | 2 to 3 |3 to 2 | 2 to 3 |3 to 4

How to read aaaaaaabaaaaaaaaaaaaaaaab?

0 to 4 | 4 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 2 | 2 to 3 | 3 to 4 | 4 to 2 | 2 to 3 | 3 to 2 |2 to 3 | 3 to 2 |2 to 3 | 3 to 2 |2 to 3 | 3 to 2 |2 to 3 | 3 to 2 |2 to 3 | 3 to 2 |2 to 3 | 3 to 2 |2 to 3 |3 to 4

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.