Algorithms for Compiler Design: EXAMPLES OF FINITE AUTOMATA CONSTRUCTION

EXAMPLE 1

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 1.

Figure 1: Transition diagram for Example 1 finite automata.

EXAMPLE 2

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.

Figure 2: Finite automata containing even number of zeros and odd number of ones.

EXAMPLE 3

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 3.

Figure 3: Finite automata containing odd number of zeros and even number of ones.

EXAMPLE 4

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 4.

Figure 4: Example 4 finite automata considers the set prefix.

EXAMPLE 5

Construct a finite automata for accepting all possible strings of zeros and ones that do not contain 101 as a substring.

Figure 5 shows a transition diagram of the finite automata that accepts the strings containing 101 as a substring.

Figure 5: Finite automata accepts strings containing the substring 101.

A DFA equivalent to this NFA will be:

�	0	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}	q0
{A, B}	q1
{A, C}	q2
{A, B, D}	q3
{A, C, D}	q4
{A, D}	q5

The transition diagram of this automata is shown in Figure 6.

Figure 6: DFA using the names A-D and q₀₋₅.

The complement of the automata in Figure 6 is shown in Figure 7.

Figure 7: Complement to Figure 6 automata.

After minimization, we get the DFA shown in Figure 8, because states q₃, q₄, and q₅ are nondistinguishable states. Hence, they get combined, and this combination becomes a dead state and, can be eliminated.

Figure 8: DFA after minimization.

EXAMPLE 6

Construct a finite automata that will accept those strings of decimal digits that are divisible by three (see Figure 9).

Figure 9: Finite automata that accepts string decimals that are divisible by three.

EXAMPLE 7

Construct a finite automata that accepts all possible strings of zeros and ones that do not contain 011 as a substring.

Figure 10 shows a transition diagram of the automata that accepts the strings containing 101 as a substring.

Figure 10: Finite automata accepts strings containing 101.

A DFA equivalent to this NFA will be:

�	0	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}	q0
{A, B}	q1
{A, C}	q2
{A, D}	q3
{A, B, D}	q4
{A, C, D}	q5

The transition diagram of this automata is shown in Figure 11.

Figure 11: Finite automata identified by the name states A-D and q₀₋₅.

The complement of automata shown in Figure 11 is illustrated in Figure 12.

Figure 12: Complement to Figure 11 automata.

After minimization, we get the DFA shown in Figure 13, because the states q₃, q₄, and q₅ are nondistinguishable states. Hence, they get combined, and this combination becomes a dead state that can be eliminated.

Figure 13: Minimization of nondistinguishable states of Figure 12.

EXAMPLE 8

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 14.

Figure 14: Automata that accepts binary strings that are divisible by three.