Finite automata for Language of all strings ending with b
Acceptable strings:
All strings of the following pattern must be accepted by the finite automata. For example, acceptable strings are b, ab, bb,bab, aaab, abab, babb,…… and all such strings with ending letter b. If any of the string that is not ending with b, and acceptable by finite automata machine, then the machine is wrong and wrong machine can read the invalid strings. Invalid strings are strings that are part of the language.
Rejectable strings:
All strings of the following pattern must not be accepted by the finite automata. For example, rejectable strings are a, ba, aa,bba, abaa,abba, baba,…… and all such strings with ending letter other than b. If any of the string that is not ending with b, and acceptable by finite automata machine, then machine is wrong and wrong machine can read the invalid strings. Invalid strings are strings that are part of the language.
In other words, we can say that all acceptable strings(100%) that are part of the language must be accepted(100%) by finite automata machine and all rejectable strings(100%) that must not be the part of the language and are rejected (100%) by finite automata machine, then the machine is OK, otherwise machine is not OK.
In this example;
The machine can read many a’s when the machine starts. After reading a, the machine can read b and can move to a state(end2). Here from state(end2) machine have two options.
- The machine can read many b’s and remain stay on state(end2). Or
- The machine can read a and move to a state(start1).
Here, we can see that machines can pick the alphabet of its own choice but all the strings machine reads are part of our defined language “Language of all strings ending with b”.
The machine can finish its execution at the ending state and the ending state is stated (end2).
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.
- DFA for (a+b)* (a+b)a .
- DFA for (bb)*(aa)* .
- DFA for b+a(a+b)*+a.
- DFA for (a+b)*b+(bb)*a.
- DFA for bb+a(a+b)*+aa.
- DFA for a(a+b)*+bb(a)* .
- DFA for a(a+b)b*+bb(a)*.
- DFA for b(aa)*a+a(bb)*b.
- DFA for a+a(aa+b)*(aa)b.
- DFA for a+a(aa+b)*+(aa)b.
- DFA for (a+b)b(a+b)*+(aa)*b.
- FA for strings starting with a and ending with a.
- FA for the language of all those strings starting with a.
- FA for the language of all those strings containing aa as a substring.
- DFA for the language of all those strings starting and ending with the same letters.
- DFA for the language of all those strings starting and ending with different letters.
- DFA for the language of all those strings having double 0 or double 1.
- DFA for the language of all those strings starting and ending with b.
- DFA for ending with b.
- DFA for the string of even A’s and even b’s.
- DFA for the regular expression of a(a+b)*+(bb)+a(ba)*+aba+bb*(a+b)*.
- RegExp and DFA for strings having triple a’s or triple b’s.
