Construct a finite automata accepting the set of all strings of zeros and ones, with at most one pair of consecutive zeros and at most one pair of consecutive ones.
A transition diagram of the finite automata accepting the set of all strings of zeros and ones, with at most one pair of consecutive zeros and at most one pair of consecutive ones is shown in Figure 2.11.
Construct a finite automata that will accept strings of zeros and ones that contain even numbers of zeros and odd numbers of ones.
A transition diagram of the finite automata that accepts the set of all strings of zeros and ones that contains even numbers of zeros and odd numbers of ones is shown in Figure 2.12.
Construct a finite automata that will accept a string of zeros and ones that contains an odd number of zeros and an even number of ones.
A transition diagram of finite automata accepting the set of all strings of zeros and ones that contains an odd number of zeros and an even number of ones is shown in Figure 2.13.
Construct the finite automata for accepting strings of zeros and ones that contain equal numbers of zeros and ones, and no prefix of the string should contain two more zeros than ones or two more ones than zeros.
A transition diagram of the finite automata that will accept the set of all strings of zeros and ones, contain equal numbers of zeros and ones, and contain no string prefixes of two more zeros than ones or two more ones than zeros is shown in Figure 2.14.
Construct a finite automata for accepting all possible strings of zeros and ones that do not contain 101 as a substring.
Figure 2.15 shows a transition diagram of the finite automata that accepts the strings containing 101 as a substring.
A DFA equivalent to this NFA will be:
| 1 | |
{ A } | { A } | { A , B } |
{ A , B } | { A , C } | { A , B } |
{ A , C } | { A } | { A , B , D } |
{ A , B , D }* | { A , C , D } | { A , B , D } |
{ A , C , D }* | { A , D } | { A , B , D } |
{ A , C , D }* | { A , D } | { A , B , D } |
Let us identify the states of this DFA using the names given below:
{ A } | q _{ } |
{ A , B } | q _{ 1 } |
{ A , C } | q _{ 2 } |
{ A , B , D } | q _{ 3 } |
{ A , C , D } | q _{ 4 } |
{ A , D } | q _{ 5 } |
The transition diagram of this automata is shown in Figure 2.16.
The complement of the automata in Figure 2.16 is shown in Figure 2.17.
After minimization, we get the DFA shown in Figure 2.18, because states q _{ 3 } , q _{ 4 } , and q _{ 5 } are nondistinguishable states. Hence, they get combined, and this combination becomes a dead state and, can be eliminated.
Construct a finite automata that will accept those strings of decimal digits that are divisible by three (see Figure 2.19).
Construct a finite automata that accepts all possible strings of zeros and ones that do not contain 011 as a substring.
Figure 2.20 shows a transition diagram of the automata that accepts the strings containing 101 as a substring.
A DFA equivalent to this NFA will be:
| 1 | |
{ A } | { A , B } | { A } |
{ A , B } | { A , B } | { A , C } |
{ A , C } | { A , B } | { A , D } |
{ A , D }* | { A , B , D } | { A , D } |
{ A , B , D }* | { A , B , D } | { A , C , D } |
{ A , C , D }* | { A , B , D } | { A , D } |
Let us identify the states of this DFA using the names given below:
{ A } | q _{ } |
{ A , B } | q _{ 1 } |
{ A , C } | q _{ 2 } |
{ A , D } | q _{ 3 } |
{ A , B , D } | q _{ 4 } |
{ A , C , D } | q _{ 5 } |
The transition diagram of this automata is shown in Figure 2.21.
The complement of automata shown in Figure 2.21 is illustrated in Figure 2.22.
After minimization, we get the DFA shown in Figure 2.23, because the states q _{ 3 } , q _{ 4 } , and q _{ 5 } are nondistinguishable states. Hence, they get combined, and this combination becomes a dead state that can be eliminated.
Construct a finite automata that will accept those strings of a binary number that are divisible by three.
The transition diagram of this automata is shown in Figure 2.24.