Finite automata FA for the language of all those strings starting and ending with same letters in theory of automata

By: Prof. Fazal Rehman Shamil
Last modified on April 14th, 2021

Built the Finite automata (FA) for the language of all those strings beginning and ending with same letters and having length two or more?

Let’s start drawing the FSA for the given language.

FA in theory of computation

To check that our FSA is correct or not, we need to check all the accepted and rejected strings. All strings that are part of the language must be accepted and all those languages that are not part of the language must be rejected by FSA.

Accepted Strings
You should check some small, some medium and some large size strings that are part of the language and all of them(100% strings) should be accepted by our FA.
Small strings:

aa, bb, aba, bab, …… and all those strings beginning and ending with same letters and having length two or more.

Medium size strings:

abaaababa,  babababaab……and all such strings that are starting and ending with the same letter and having a length of string two or more

Large size strings:

ababbabaaabaabbba, baababbbbaaababababb,…….and all such strings that are starting and ending with the same letter and having a length of string two or more.

 

Rejected Strings
You should check some small, some medium and some large size strings that are not part of the language and all of them(100% strings) should be rejected by our FA.

Small strings:

a, b, ab, ba, abb, baa….. and all such strings that are not starting and ending with the same letter and does not have a length of string two or more.

Medium size strings:

ababab, bababbaba ……and all such strings that are not starting and ending with the same letter and does not have a length of string two or more.

Large size strings:

ababbababababbabababbabab,   bababababbabbbaaaaba…….and all such strings that are not starting and ending with the same letter and does not have the length of string two or more.

List of 100+ Important Deterministic Finite Automata

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.