FA in theory of computation

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

By: Prof. Dr. Fazal Rehman | Last updated: April 3, 2022

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.

Explanation of FA for the language of all those strings starting and ending with same letters
Explanation of FA for the language of all those strings starting and ending with same letters
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.
Valid and invalid strings of DFA for the language of all those strings starting and ending with same letters
Valid and invalid strings of DFA for the language of all those strings starting and ending with same letters

 

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

fyp ideas main page

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.

Related Posts:

Leave a Comment

All Copyrights Reserved 2025 Reserved by T4Tutorials