2. Finite Automata – Formal Languages and Automata Theory

2

Finite Automata

In this chapter, we introduce the definition of Finite Automaton (FA) and also some real-time problems that can be solved using FA. Representation of FA is done using 5-tuple form, transition table and transition diagram. Definitions of non-deterministic and deterministic FAs are explained with examples and, further, how these automata act as language acceptor is elaborated. Equivalence of NFAs-with-ɛ to NFAs-without-ɛ, and equivalence of NFAs to DFAs are explained. Minimizing the given automaton using Myhill Nerode and π construction method, and testing the equivalence of two FAs are discussed. Moore and Mealy machines, which represent Finite Automaton with output, are explained with examples.

2.1  Finite-state Machine

The finite-state system represents a mathematical model of a system with some input. The model finally gives some output. The input supplied to the machine is processed by various states. These states are called intermediate states.

Good example of finite-state systems is a control mechanism of elevator. This mechanism remembers only the current floor number pressed; it does not remember any of the previously pressed numbers.

Another good example is a bulb operated with a single switch. Switch has two possibilities: it closes or opens the circuit. When the circuit is closed the current passes and the bulb glows.

From the above statement it is clear that the bulb will be either in ON state or OFF state. If it is in ON state and if the current passes through it, then the bulb will glow. If no current is passed then it changes to OFF state. The flow of current is indicated by value 1, and blocked state of current flow is indicated by 0. The functioning of the bulb can be shown in the form of a table:

State
Current = 1
Current = 0
ON
ON
OFF
OFF
ON
OFF

This is a finite system that represents the functioning of a bulb. Many real-time problems can be represented using such mathematical models.

The finite-state systems are useful in designing text editors, lexical analysers and natural language processing.

Definition 1: A finite automaton is formerly defined as a 5-tuple (Q, ∑, δ, q0, F) where

Q

is a finite set of states which is non-empty

is the input alphabet

q0

is the initial state

F

is a set of final states and F ⊆ Q

δ

is a transition function or mapping function Qx ∑ → Q using this the next state can be determined depending on the current input.

2.1.1  Finite-Automaton Model

The finite automaton can be represented as input tape and finite control as shown in the Figure 2.1:

  1. Input tape: is a linear tape having some cells that can hold an input symbol from ∑.
  2. Finite control: The finite control indicates the current state and it decides on the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left to right, and at any instance only one input symbol is read.

Fig 2.1   Finite Automaton

The reading head examines the read symbol, and the head moves to the right with or without changing the state. When the entire string is read, if finite control is in final state, the string is accepted; else it is rejected. Finite automaton can be represented by the transition diagram, in which the vertices represent the states and edges represent transitions. We can model the real-word problems as a finite automaton and this helps in understanding the behaviour and in analysing the behaviour.

Fig 2.2   Combinational Circuit

Example 2.1

Consider the following combinational circuit shown in Figure 2.2 represent the circuit using finite state system.

A circle with * (or ) represents AND gate, represents OR gate and represents inverter or NOT gate. By changing the signals at U1, U2 and i/p signal x we get output Z1* Z2. This behaviour can be shown as an FA:

If output expected is 1, then states [11] become an accepting state of the finite automaton. Figure 2.3 gives a simple model of a combinational circuit, which helps us in analysing the behaviour, by changing signal at Z1Z2.

U1 U2

0

1

z1 z2

z1 z2

0

0

1

1

11

1

11

11

10

10

0

10

Fig 2.3   Finite Automaton For Combinational Circuit

Example 2.2

Lexical analyser behaviour can be shown as an FA. Consider the lexical analyser that matches words such as ‘the’, ‘this’, ‘that’, ‘to’ shown as FA in Figure 2.4.

Fig 2.4   Simple Lexical Analyzer

These systems are called finite automaton as the number of possible states and the number of letters in the alphabet are, both, finite. It is automaton because the change of state is totally governed by the input.

2.1.2  Properties of Transition Function ‘x’

The transition function δ defined as Q × ∑→ Q holds the following properties for all states q ∈ Q and a ∈ ∑*

  1. δ (q, ε) = q. The states of the FA are changed only by an input symbol.
  2. For all strings w and i/p symbol a,

     

    δ (q, aw) = δ (δ (q, a), w)

     

    An FA can be represented by a

    1. Transition diagram
    2. Transition table

2.1.3  Transition Diagram

A transition graph contains

  1. Set of states as circles

    Start state q0 with arrow

    Final state by double circle (Figure 2.5).

    Fig. 2.5 Representation of Final States

  2. A finite set of transitions (edges|labels) that shows how to go from one state to another state as shown in Figure 2.6.

2.1.4  Transition Table

Following is a tabular representation where rows correspond to states and columns correspond to input. Start state is given by → and the final state by *

Example 2.3

M = {{q0, q1, q2}, {a, b}, δ, q0, {q2}}

δ (q0, a) = q1

δ (q0, b) = q2

δ (q1, a) = q2

δ (q1, b) = q0

δ (q2, a) = q2

δ (q2, b) = q2

Δ/Σ
b
→ q0
q1 
q2
q1
q2
q0 
*q2
q2
q2

The same table can be shown as a transition diagram (Figure 2.6)

Fig 2.6   Transition Diagram

2.2  Language Acceptance

A string w is accepted by finite automaton U = {Q, ∑, δ, q0, F} if δ (q0, w) = P for some P in F. This concludes that string is accepted when it enters into the final state on inputting the last element.

Example 2.4

Let us check if the input string 1010 is accepted or not: by FA shown in Figure 2.7.

 

δ(q0, 1010) = δ (q2, 010) = δ (q3, 10) = δ (q1, 0) = q0

Here q0 is the final state. Hence, the string is accepted.

b) Check 11111

q2 ∉ F. Hence, this string is rejected.

Fig 2.7  Finite Automaton

Example 2.5

Give the language defined by the following FA: shown in Figure 2.8.

If we list the different strings accepted by this automata, we get

{1, 01, 0001, 10101, 011111………………}

We observe that all the strings accepted are ending with 1.

 

L(M) = {w/w ends with 1 on ∑ = {0, 1}}.

 

Language accepted by machine M (denoted by L(M)) is given by the set of strings that are ending with 1.

Fig 2.8  FA for Example 2.5

Example 2.6

Identify the language defined by following machine: in Figure 2.9.

In this automaton, since the initial state and the final state are same, it accepts ε and all strings that end with 0. Hence the language accepted by this L(M) = {w/w is ε or all strings that end with 0}

or

L(M) = {w/w is ε or all strings that do not end with 1}

Fig 2.9  FA for Example 2.6

Example 2.7

Identify the language defined by following machine:in Figure 2.10.

Fig 2.10  FA for Example 2.7

Solution:

The strings valid in the language are

L = {a, aa, aba, abba, aaa, ……
b, bb, bab, bbb, baab, ........}

L(m) = {w/w contains all strings that start and end with same symbol}

2.3  Two Types of Finite Automata

  1. Deterministic finite automata (DFA)
  2. Non-deterministic finite automata (NFA)

In DFA, there will be a unique transition in any state on an input symbol. In NFA, there can be more than one transition on an input symbol. Hence, DFA is faster than NFA. The Figure 2.10 is an example of a DFA. The Figure 2.11 is an example of NFA.

In Figure 2.11 in state q0 on 0, it is either in state q0 or in state q1. Hence it is a NFA.

Fig 2.11  Non Deterministic Finite Automaton

2.3.1  Deterministic Finite Automata (DFA)

Definition 2: Deterministic finite automata can be defined as quintuple

 

where

M = (Q, ∑, δ, q0, F)

Q = a non-empty finite set, of states

∑ = input alphabet

q0 = initial start state

F = set of final states

δ = transition function that takes two arguments, a state and an input symbol, and returns output as state, that is, δ: Q × ∑ → Q

Example: δ (q1, a) = q1

DFA can be used as finite acceptor because its sole job is to accept certain input strings and reject others.

It is also called language recognizer because it merely recognizes whether the input strings are in the language or not.

Example 2.8

Design a DFA which accepts only input 101 over the set {0, 1}

Fig 2.12  FA with Trap State

Solution: Here qtrap is called trap state/dummy state where unnecessary transitions are thrown away (Figure 2.12).

Example 2.9

Design a DFA that accepts even number of 0’s and even number of 1’s.

Solution: This FA will have four different possibilities:

Even number of 0’s and even number of 1’s – q0

Odd number of 0’s and even number of 1’s – q1

Even number of 0’s and odd number of 1’s – q2

Odd number of 0’s and odd number of 1’s – q3

where states are q0, q1, q2 and q3. Since the state q0 indicates the condition of even number of 0’s and even number of 1’s, this state is made the final state. The DFA is given by Figure 2.13.

Fig 2.13  DFA for Example 2.9

Example 2.10

Design a DFA that accepts all the strings with at most 3 a’s.

Solution: Strings that have more than three a’s should not be accepted. There are five possibilities. Hence, the DFA requires five states:

No a’s

– q0 (Accepting state)

One a

– q1 (Accepting state)

Two a’s

– q2 (Accepting state)

Three a’s

– q3 (Accepting state)

Four a’s

– q4 (for dummy state indicating a non-accepting state)

Deterministic finite automata can be constructed by expanding the listed conditions as shown in Figure 2.14.

Fig 2.14  DFA for Example 2.10

Example 2.11

Draw a DFA that recognizes the set of all strings starting with prefix ab with alphabets from ∑ = {a. b}.

Solution: This automaton should accept strings that start with ab (and then followed by arbitrary elements). It should reject strings that start with b. Hence, if it sees b at the initial state, it should enter the dead state, from which there is no path to the final state. After a, it should find b. Hence, in the second state if it sees a, it should enter the dead state. Once it sees ab, it is the final state and remains in the same state on any element. Figure 2.15 shows the resultant DFA.

Fig 2.15  DFA for Example 2.11

Example 2.12

Design a DFA that accepts even number of a’s over ∑ = {a}.

Solution: This automaton should accept strings that have even number of a’s. On seeing a’s which form an even count, the DFA should be in final state and on seeing odd count of a’s, it should be in non-final state as shown in Figure 2.16.

Fig 2.16  DFA for Example 2.12

Fig 2.17  DFA for Example 2.12 With More States

This DFA is not unique. The same machine can also be designed as in Figure 2.17.

Both DFAs represent the same language but with different number of states. It is always better to have less number of states as it simplifies the implementation.

Example 2.13

DFA that accepts odd number of 1’s on {0, 1}.

Solution: This automaton should accept strings that have odd number of 1’s and any number of 0’s. On seeing 1’s that form an odd count, the DFA should be in the final state and, on seeing even count of 1’s, it should be in non-final state as shown in Figure 2.18.

Fig 2.18  DFA for Example 2.13

Example 2.14

Design a DFA that contains 001 as substring in all strings over ∑ = {0, 1}.

This automaton should accept strings that have substring ‘001’. On seeing ‘0’ go to next q1 state, otherwise be in same state. In q1 state, on seeing ‘0’, go to next q2 state; otherwise go to the initial state, as the substring would not be ‘00’. In q2 state, on seeing ‘1’, go to next q3 state, otherwise be in same state, as it would satisfy the required condition that 1 should be preceded by ‘00’. Declare q3 as final state, as the required total condition is satisfied and is shown in Figure 2.19.

Fig 2.19  DFA for Example 2.14

2.3.2  Non-deterministic Finite Automaton (NFA)

In this automaton, for a given input symbol, there can be more than one transition from a state. Such automaton is called Non-deterministic Finite Automaton. NFA is mathematically described as a quintuple.

Definition 3: Non-deterministic finite automata can be defined as quintuple

 

where

M = (Q, ∑, δ, q0, F)

Q = Non-empty finite set of states

∑ = input alphabet which includes

q0 = initial start state

F = set of final states

δ = transition function that takes two arguments (a state and an input symbol) and returns an output as state, that is, δ: Q X ∑ →2Q

2.3.3  Acceptance of NFA

Acceptance of a string is defined as ‘reaching final states on processing the input string’ i.e. if there exits atleast one path from start state to final state, then the string is accepted by NFA.

Check if 0100 is accepted or not. by automata in Figure 2.20.

Fig 2.20  Simple NFA

As there is a path from q0 to final state qn the string is accepted. Thus we check all possible paths from start state.

Note: It is easy to construct a NFA than a DFA. But for a given string, the processing time of NFA is greater than that of a DFA.

Example 2.15

Design NFA for {ababn/n > = 0}

Solution: Read the sequence a, b, a in state q0 and q1, q2 and q3 in sequence. Since bn, n ≥ 0 indicates zero or more no of b’s in state q3 add self loop in this state and declare it as final state and is shown in Figure 2.21.

Fig 2.21  NFA for Example 2.15

Example 2.16

Design NFA for the set of strings such that 5th symbol from right end is 1.

Solution: Since fifth symbol from right end is 1, we can have minimum 6 states.

The first transition should be on 1, remaining can be either 0 or 1 and is shown in Figure 2.22.

Fig 2.22  NFA for Example 2.16

Example 2.17

Design a NFA and DFA accepting all the strings ending with 01 over ∑ = {0, 1}

Solution: We can have any string on 0 or 1 but it should end with 0 followed by 1. The corresponding NFA is shown in Figure 2.23.

Fig 2.23  NFA for Example 2.17

Corresponding DFA is shown in Figure 2.24.

Fig 2.24  DFA for Example 2.17

So drawing NFA is simpler than drawing DFA.

2.4  Equivalence of DFAs and NFAs

Theorem 1: Let L be a set accepted by a NFA. Then there exists a DFA that accepts L.

Proof: Let M = (Q, ∑, δ, q0, F) be a NFA accepting L.

Define DFA M1 = (Q1, ∑ 1, δ1, q01, F1) as follows.

The states of M1 are all the subsets of the set of states of M, that is, Q1 = 2Q.

If Q = {A, B} then Q1 = {φ, [A], [B], [AB]}. F1 is the set of all states in Q1 containing a final state of M. If F = {B} then F1 = {[B], [AB]}.

An element of Q1 will be denoted by [q1, q2,……qi] where q1, q2,……qi are in Q.

Note: [q1, q2,…qi] is a single state of DFA corresponding to the set of states of NFA.

q01 = [q0]

We define δ1 ([q1, q2,…qi], a) = [P1, P2,…..Pi]

iff δ ({q1, q2,…qi}a) = {P1, P2,...Pi},

that is, δ1 applied to an element [q1, q2,…qi] of Q1 is computed by applying δ to each state of Q represented by [q1, q2,…qi]. It is easy to show by induction on length of the input string x that

δ1 (q01, x) = [q1, q2,…qi]
iff δ (q0, x) = {q1, q2,…qi}

Basis: The result is trivial for |x| = 0. As δ (q01, ε) = [q0] ⇒ q01 = [q0]

Induction: Suppose that the hypothesis is true for inputs of length m or less. Let ‘xa’ be a string of length m + 1 with a in ∑. Then

δ1(q0, xa) = δ11(q0, x), a)

By inductive hypothesis

δ1(q0, x) = [P1, P2,…..Pj]
iff δ(q0, x) = {P1, P2,….Pj}

But by the definition of δ1

δ1([P1, P2,….Pj]a) = [r1, r2,….rk}

Thus

δ1(q01, xa) = [r1,r2,….rk]
iff δ (q0, xa) = {r1, r2,….rk}

This establishes the inductive hypothesis.

Now we have to prove that the L(M) = L(M1).

The string x is accepted by NFA or DFA only if it is in one of the final states.

For a string x in NFA, let δ (q0, x) = P where P ∈ F. Then δ1(q0, x) = [P] where [P] ∈ F1, Hence,the string x is accepted if it is accepted by NFA.

Note

  • Every language that can be described by NFA can be described by some DFA
  • DFA in practice has more states than NFA
  • DFA equivalent to NFA can have at most 2n states whereas NFA has only n states.

2.5  Converting NFA (MN) to DFA (MD)— Subset Construction

Let MN = (QN, ∑N, δn, qON, FN) be the given NFA to construct equivalent DFA MD. Define

MD as follows.

  1. QD = 2QN. If NFA has n states, DFA can have at most 2n states.
  2. n = ∑D
  3. [q0] = {qn}
  4. FD = Set of all states of QD that contains at least one of the final states of FN.
  5. δD((q1, q2, q3), a) = δn(q1, a) ∪ δn (q2, a) ∪ δn(q3, a)
    = {P1, P2, P3} say

Add the state [P1, P2, P3] to QD if it is not there.

Example 2.18

Convert the NFA shown in the Figure 2.25 to DFA.

Fig 2.25  NFA

Solution:

Step 1: Find the possible set of states Q.

Then Q has 22 (= 4) states, and it is the set of all subsets of q0, q1:

{Ø, [q0], [q1], [q0q1]}

Step 2: Find the initial state.

[q0 ] = q0

Step 3: Define the transitions on 0, 1, on each state.

δ(q0, 0) = [q0, q1]

δ(q0, 1) = [q1]

δ(q1, 0) = [q1]

δ(q1, 1) = [q0, q1]

δ([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = [q0, q1]

δ([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = [q0, q1]

F = The set of states that contain q0, called the final states in DFA. [q0], [q0, q1]

Step 4: Transition diagram of the DFA is shown in Figure 2.26. In the set of states, we have not used the state Ø as it is not reached.

Fig 2.26   Equivalent DFA

Example 2.19

Convert the NFA in Figure 2.27 to DFA.

Solution:

Q has 23 (= 8) states, and it is the set of all subsets of q0, q1, q2:

{Ø, [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2]}

∑ = 0, 1

q0 = [q0]

F = {[q2], [q0, q2], [q1, q2], [q0, q1, q2]}

δ is given by δD([q1 q2], a) = δn (q1, a) U δn (q2, a)

where δn is transition function of NFA

Fig 2.27    NFA

δ

0

1

Ø

Ø

Ø

[q0]

[q0, q1]

[q0]

[q1]

Ø

[q2]

[q2]

Ø

Ø

[q0, q1]

[q0, q1]

[q0, q2]

*[q0, q2]

[q0, q1]

[q0]

[q1, q2]

Ø

[q2]

[q0, q1, q2]

[q0, q1]

[q0, q2]

The states φ, [q1], [q2], [q1, q2] and [q0, q1, q2] are not reachable from start state. Hence, they cannot define any string. So they can be thrown away. Hence the DFA can be simplified as in Figure 2.28.

Fig 2.28    Equivalent DFA for Example 2.19

To get this simplified DFA, construct the states of DFA as follows:

  1. Start with the initial state. Do not add all subsets of states as there may be unnecessary states.
  2. After finding the transition on this initial state, include only the resultant states into the list until no new state is added to the list. For example, if δ(q0, a) = {q0, q1} (say), then add this as a new state in DFA and find the transition from this state on the input symbol.
  3. Declare the states as final if they have at least one final state of the NFA.
Example 2.20

Convert the following NFA to a DFA.

 

δ
0
1

→q0

{q1 q2}

{q0}

q1

{q0 q1}

Ø

*q2

{q1}

{q0 q1}

Solution: DFA is

Q has 23 (= 8) states, and it is the set of all subsets of q0, q1, q2:

{Ø, [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2]}

∑ = 0, 1

q0 = [q0]

F = {[q2], [q0, q2], [q1, q2], [q0, q1, q2]}

δ
0
1

→[q0]

[q1 q2]

[q0]

*[q1 q2]

[q0 q1]

[q0 q1]

q0 q1]

[q0 q1 q2]

[q0]

*[q0 q1 q2]

[q0 q1 q2]

[q0 q1]

The transition diagram of DFA is as shown in Figure 2.29.

Fig 2.29    DFA for Example 2.20

2.6  NFA with Epsilon- (ɛ) Transitions

We can extend a NFA by introducing ‘ɛ-moves’ that allow us to make a transition on the empty string. There would be an edge labelled ɛ between two states and this edge allows transition from one state to another even without receiving an input symbol. This is another mechanism that allows NFA to be in multiple states at once. Constructing such NFA is easy, but the NFA thus constructed is not that powerful. The NFA with ɛ-moves is given by M = (Q, ∑, δ, q0, F) where δ is defined as Q X ∑ ∪ {ɛ} → 2Q.

Example 2.21

Figure 2.30 gives NFA with ɛ transitions and it accepts strings of the form {0n1m2o/n, m, o ≥ 0}, that is, any number of 0’s followed by any number of 1’s followed by any number of 2’s.

Fig 2.30    NFA with ɛ-Transitions

Example 2.22

Design NFA for language L = {0K | k is multiple of 2 or 3}.

NFA for set of strings that have the characteristic that the number of 0’s in them is a multiple of 2 is given in Figure 2.31.

NFA for set of strings that have the characteristic that the number of 0’s in them is a multiple of 3 is given in Figure 2.32.

Fig 2.31    NFA for 02k

Fig 2.32    NFA for 03k

Combining these two NFAs, we get Figure 2.33.

Fig 2.33  NFA for 02k /03k

2.6.1  Epsilon Closure (ɛ-closure)

Epsilon closure of a state is simply the set of all states that we can reach by ɛ input. This is denoted by either (q) or ɛ-closure (q). In Figure 2.30: the epsilon closure of q0, q1, q2 states are

 

ɛ-closure (q0) = {q0, q1, q2}

ɛ-closure (q1) = {q1, q2}

ɛ-closure (q2) = {q2}

Let us define the extended transition function for a NFA with ɛ transitions. For a regular NFA, for the induction step we defined

(q, w) = {p1, p2, ... pk}
(pi, a) = Si for i = 1, 2,...k

Then, we defined (q, wa) = S1 ∪ S2 ∪... ∪ Sk.

For a NFA with ɛ, we change for the definition of (q, wa) as follows:

(q, wa) = ∪ ɛ-closure(S1 ∪ S2 ∪... ∪ Sk)

This new definition includes the original sets S1, S2..., Sk as well as the states we can reach via ɛ transitions from these states.

 

2.6.2  Eliminating ɛ-Transitions

ɛ-Transitions are used for convenience in some cases, but they do not increase the power of the NFA. To eliminate them, we can convert a NFA with ɛ into an equivalent NFA without ɛ, by eliminating the ɛ edges and replacing them with the edges labelled with symbols present in Σ. We can also convert NFA with ɛ into an equivalent DFA, by steps quite similar to those we took for converting a normal NFA to a DFA, except that we must now follow all ɛ-transitions and add those to our set of states.

2.6.3  Converting NFA with ɛ-Transition to NFA without ɛ-Transition

For each state compute ɛ-closure(q) on each input symbol a ∈ Σ. If the ɛ-closure of a state contains a final state then make the state final.

Let us consider the NFA with ɛ-transitions depicted in Figure 2.34.

Fig 2.34   NFA with t

The transition table is

Step 1: Find ɛ-closure of each state.

ɛ-closure (q0) = {q0, q1, q2}
ɛ-closure (q1) = {q1, q2}
ɛ-closure (q2) = {q2}

Step 2: Find the transition on each state for each element.

(q0, 0) = ɛ-closure (δ(ɛ-closure (q0), 0))
= ɛ-closure (δ({q0, q1, q2}, 0))
= ɛ-closure ({q0}, ∪{Ø}, ∪{Ø})
= {q0, q1, q2}
(q0, 1) = ɛ-closure (δ(ɛ-closure (q0), 1))
= ɛ-closure (δ({q0, q1, q2}, 1))
= ɛ-closure ({Ø}, ∪{q1}, ∪{Ø})
= {q1, q2}
(q0, 2) = ɛ-closure (δ(ɛ-closure (q0), 2))
= ɛ-closure (δ({q0, q1, q2}, 2))
= ɛ-closure ({Ø}, ∪{Ø}, ∪{q2})
= {q2}
(q1, 0) = ɛ-closure (δ(ɛ-closure (q1), 0))
= ɛ-closure (δ({q1, q2}, 0))
= ɛ-closure ({Ø})
= {Ø}
(q1, 1) = ɛ-closure (δ(ɛ-closure (q1), 1))
= ɛ-closure (δ({q1, q2}, 1))
= ɛ-closure ({q1}, ∪{Ø})
= {q1, q2}
(q1, 2) = ɛ-closure (δ(ɛ-closure (q1), 2))
= ɛ-closure (δ({q1, q2}, 2))
= ɛ-closure ({Ø}, ∪{q2})
= {q2}
(q2, 0) = ɛ-closure (δ(ɛ-closure (q2), 0))
= ɛ-closure (δ({q2}, 0))
= ɛ-closure ({Ø})
= {Ø}
(q2, 1) = ɛ-closure (δ(ɛ-closure (q2), 1))
= ɛ-closure (δ({q2}, 1))
= ɛ-closure ({Ø})
= {Ø}
(q2, 2) = ɛ-closure (δ(ɛ-closure (q2), 2))
= ɛ-closure (δ({q2}, 2))
= ɛ-closure ({q2})
= {q2}

NFA without ɛ-transitions is

Transition diagram of this NFA without ɛ-transitions is given in Figure 2.35.

Fig. 2.35  NFA without ε

2.6.4  Converting NFA withɛ-transition to DFA

  1. Compute ɛ* for the current state, and this results in a set of states S.
  2. δ(S, a) is computed for all a ∈ Σ by the following steps:
    1. Let S = {p1, p2, ... pk}
    2. Compute R = δ(S, a) by

      This set is achieved by following input a, not by following any ɛ-transition.

    3. Add the ɛ-transitions by computing ɛ-closure(R).
  3. Make a state an accepting state if it includes any final state in the NFA.

Note: The ɛ (epsilon)-transition refers to a transition from one state to another without reading any input symbol (i.e. without the tape containing the input string moving). Epsilon transitions can be inserted between any two states.

Consider the NFA- ɛ move machine M = {Q, Σ, δ, q0, F}.

Q = {q0, q1, q2}

Σ = {a, b, c} and ɛ moves

DFA construction

Step 1: Q has 23 (= 8) states, and it is the set of all subsets of all subsets of q0, q1, q2:

{Ø, [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2]}
∑ = 0, 1, 2
q0 = (q0)
F = {[q2], [q0, q2], [q1, q2], [q0, q1, q2]}

Step 2: Compute ɛ-closure of each state.

(q0)= {q0, q1, q2}
(q1) = {q1, q2}
(q2) = {q2}

Step 3: Find the initial state by finding the ɛ-closure of the initial state.

q0 = (q0) = [q0, q1, q2]

Step 4: Explore the states that are valid states in DFA starting at the new initial state. Explore each new state by finding the transitions on every input element:

([q0, q1, q2], 0) = ɛ-closure (δ([q0, q1, q2], 0))
= ɛ-closure (δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0))
= ɛ-closure ({q0} ∪ {Ø} ∪ {Ø})
= [q0, q1, q2]
([q0, q1, q2], 1) = ɛ-closure (δ([q0, q1, q2], 1))
= ɛ-closure (δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1))
= ɛ-closure ({Ø} ∪ {q1} ∪ {Ø})
= [q1, q2]
([q0, q1, q2], 2) = ɛ-closure (δ([q0, q1, q2], 2))
= ɛ-closure (δ(q0, 2) ∪ δ(q1, 2) ∪ δ(q2, 2))
= ɛ-closure ({Ø} ∪ {Ø} ∪ {q2})
= [q2]

The next new state is [q1, q2] and the transitions for the new states are

([q1, q2], 0) = ɛ-closure (δ([q1, q2], 0))
= ɛ-closure (δ(q1, 0) ∪ δ(q2, 0))
= ɛ-closure ({Ø} ∪ {Ø})
= [Ø]
([q1, q2], 1) = ɛ-closure (δ([q1, q2], 1))
= ɛ-closure (δ(q1, 1) ∪ δ(q2, 1))
= ɛ-closure ({q1} ∪ {Ø})
= [q1, q2]
([q1, q2], 2) = ɛ-closure (δ([q1, q2], 2))
= ɛ-closure (δ(q1, 2) ∪ δ(q2, 2)) = ɛ-closure ({Ø} ∪ {q2})
= [q2]

The third new state is [q2].

([q2], 0) = ɛ-closure (δ([q2], 0))
= ɛ-closure (δ(q2 0))
= ɛ-closure ({Ø})
= [Ø]
([q2], 1) = ɛ-closure (δ([q2], 1))
= ɛ-closure (δ(q2 1))
= ɛ-closure ({Ø})
= [Ø]
([q2], 2) = ɛ-closure (δ([q2], 2))
= ɛ-closure (δ(q2 2))
= ɛ-closure ({q2}) = [q2]

The last new state is [Ø] which is a dummy state, and the transitions are

Note: (Ø) = {Ø}

([Ø], 0) = ɛ-closure (δ([Ø], 0))
= ɛ-closure ({Ø})
= [Ø]
([Ø], 1) = ɛ-closure (δ([Ø], 1))
= ɛ-closure ({Ø})
= [Ø]
([Ø], 2) = ɛ-closure (δ([Ø], 2))
= ɛ-closure ({Ø})
= [Ø]

DFA transition table

Fig 2.36  DFA

2.7  Comparison Method for Testing Equivalence of Two FAs

Let M and M1 be two FAs over ∑. We construct a comparison table consisting of n + 1 columns where n is the number of input symbols.

  1. 1st column consists of pair of nodes of the form (q, q1) where q ∈ M and q1 ∈ M1.
  2. If (q, q1) appears in some row of 1st column, then the corresponding entry in the column of a (a ∈ ∑) is (qa, qa1) where (qa, qa1) are reachable from q and q1 on a.
  3. Table is constructed by starting with a pair of initial vertices qin and qin1 of M and M1. We complete the construction by considering the pairs that are not in 1st column but are in the 2nd and subsequent columns.
    1. If we reach a pair (q, q1) such that q is in the set of final states of M and q1 is non-final state of M1 then terminate the construction and conclude that M and M1 are not equivalent.
    2. If the construction is terminated when no new element that are not the 1st column appears in the 2nd and subsequent columns, conclude that M and M1 are equivalent. To show the equivalence, let us consider the two DFA’s as shown in the Figures 2.37 and 2.38. Start at the initial state [q0, q4].

Fig 2.37    Finite Automata for Comparision

By looking at the number of states, we cannot conclude whether they are equivalent or not.

c
d
[q0, q4]
[q3, Ø]
[q3, q5]

Since we do not have a pair (qM1qM2) for input c, M1 and M2 are not equivalent.

2.8  Reduction of Number of States in FA

  • Any DFA defines a unique language, but the converse of this is not true, that is, given a language, we cannot claim that there is a unique DFA associated.
  • For one language, there can be many DFAs. So the number of states can consierably differ. By using comparison method we test this.

2.8.1  Indistinguishable States

Two states p and q of a DFA are indistinguishable if

δ*(p, w) ∈ F implies δ*(q, w) ∈ F

and

δ*(p, w) ∉ F implies δ*(q, w) ∉ F

Or for some string w ∈ ∑* if δ*(p, w) ∈ F and

δ*(q, w) ∉ F (or vice versa), states p and q are said to be distinguishable by a string w.

2.8.2  Equivalent Classes

The concept of equivalent class is used in minimizing the number of states. States that are equivalent can be combined together into one class called equivalent class. Let us see the definition of equivalent states.

Definition 4: Two states q1 and q2 are equivalent (denoted by q1 ≡ q2) if both δ(q1, a) and δ(q2, a) are final states or both of them are non-final states for all a ∈ ∑. These states are said to be 0-equivalent.

Definition 5: Two states q1 and q2 are K-equivalent (denoted K ≥ O) if both δ(q1, x) and δ(q2, x) are final states, or both are non-final states for all string x’s of length K or less.

Therefore, any two final states are K − equivalent if they belong to the same set in K − 1 step, otherwise they are not K-equivalent.

Properties:

P1: The relation between q1 and q2 is an equivalent relation (i.e. K-equivalence relation) i.e it is reflexive, symmetric and transitive.

P2: Every equivalence relation partitions set is also K-equivalence relation partition set Q.

P3: If q1 and q2 are K-equivalent for all K ≥ 0, then they are equivalent.

P4: If q1 and q2 are (K + 1)-equivalent then they are K-equivalent.

2.8.3  Minimization of DFA

For any deterministic automaton, that has more number of states, we can construct its equivalent DFA with a less number of states. we can minimize the states of DFA as follows.

Construction of Minimum Automaton

  1. Initially construct 0-equivalence class by ∏0 = {Q10, Q20} where Q10 is the set of final states and Q20 = Q − Q10 is the set of non-final states.
  2. Construct ∏K+1 from ∏K by partitioning further:
    1. Let Q1K be any subset in ∏K. If q1 and q2 are in Q1K they are (K + 1)-equivalent provided δ(q1, a) and δ(q2, a) are K-equivalent.
    2. Find out whether δ(q1, a) and δ(q2, a) are in the same equivalence class in ∏K for every a ∈ ∑. If so, q1 and q2 are (k + 1)-equivalent. This way Qi k is further divided into (K + 1)-equivalence classes. Repeat this for every Qi k in ∏K to get all the elements of ∏K + 1.
  3. Construct ∏n for n = 1, 2, 3, … until ∏n = ∏n + 1.
  4. Construct the minimum state DFA with the states obtained by equivalent classes πn.

First approach:

Example 2.23

Find minimum finite-state automata for the DFA shown in Figure 2.38.

0
1
→a
b
f
b
g
c
*c
a
c
e
h
f
f
c
g
g
g
e
h
g
c

Fig 2.38    DFA

Any two final states are 0-equivalent, and any two non-final states are also 0-equivalent.

0 (1, 2) = {{c}, {a, b, d, e, f, g, h}}

From the above table, we find a, e, g are 1-equivalent, b, h are 1 equivalent and d, f are 1-equivalent. Hence,

1 (1, 3, 4, 5) = {{c}, {a, e, g}, {b, h}, {d, f}}

Using the new classes, we find whether they are 2-equivalent.

2 (1, 6, 7, 8, 9) = {{c},{a, e}, {b, h}, {d, f}, {g}}

3 (1, 6, 7, 8, 9) = {{c},{a, e}, {b, h}, {d, f}, {g}}

From the above two relations, ∏2 and ∏3 are same. Hence, the final set of states are the sets 1, 6, 7, 8, 9 where {a, e}, {b, h}, {d, f}, {g}, {c} are all 3-equivalent. The minimized DFA is depicted in Figure 2.39.

0
1
→{a, e}
{b, h}
{d, f}
{b, h}
{g}
{c}
*{c}
{a, e}
{c}
{d,f}
{c}
{g}
{g}
{g}
{a, e}

Fig 2.39    Minimum State DFA

Second approach:

Example 2.24

Construct the minimum DFA for the given DFA shown in Figure 2.40.

Fig 2.40    DFA

Solution: Let us represent the DFA as a transition table.

a = 0
a = 1
→q0
q1
q2
q1
q2
q4
q2
q3
q2
q3
q2
q4
*q4
q1
q4
  1. Initially we identify 0-equivalence: ∏0 = {Q10, Q20} where Q10 is the set of final states and Q20 = Q − Q10 is set of non-final states.

    Q10 = {q4}

    Q20 = {q0, q1, q2, q3}

  2. Construct ∏1 from ∏0 identifying the equivalent states in {Q10, Q20}.

    Q10 cannot be divided as it has only one state.

    Q20 has four states. We need to identify whether they are 1-equivalent.

    Compare q0, q1 on input 0 and 1

    δ(q0, 0) = q1
    δ(q1, 0) = q2

    Both of these resultant states belong to Q20.

    δ(q0, 1) = q2
    δ(q1, 1) = q4

    These resultant states belong to different sets in ∏0

    ⇒ q0 is not 1-equivalent to q1

    Compare q0, q2 on input 0 and 1

    both resultant states belong to Q20.
    both resultant states belong to Q20.
    ⇒ q0 is 1-equivalent to q2

    Compare q0, q3 on input 0 and 1

    both resultant states belong to Q20.
    both resultant states belong to different sets in ∏o.
    q0 is not 1-equivalent to q3

    Therefore,

    1 = {Q11, Q21, Q31}

    where

    Q11 = {q4}
    Q21 = {q0, q2}
    Q31 = {q1, q3}
  3. Construct ∏2 from ∏1 identifying the equivalent states in {Q11, Q21, Q31}.

    Q11 cannot be divided as it has only one state.

    Q21 and Q31 has two states each, we need to identify whether they are equivalent. Compare q0, q2 on input 0 and 1

    both resultant states are same and belong to Q31.
    both resultant states are same and belong to Q21.
    ⇒ q0 is 2- equivalent to q2

    Compare q1, q3 on input 0 and 1

    both resultant states are same and belong to Q21.
    both resultant states are same and belong to Q11.
    ⇒ q1 is 2- equivalent to q3

    Therefore,

    2 = {Q12, Q22, Q32}

    where

    Q12 = {q4}
    Q22 = {q0, q2}
    Q32 = {q1, q3}
  4. We see that Π2 is equal to Π1. The states q0 and q2 are considered a single state, denoted q02, and q1 and q3 are considered a single state, denoted q13. Minimized DFA is
    a = 0
    a = 1
    →q02
    q13
    q02
    q13
    q02
    q4
    *q4
    q13
    q4

2.8.4  Minimization of DFA Using Myhill Nerode Theorem

Myhill Nerode theorem is used if we have to prove the given language is not regular and also to eliminate useless states in the given DFA.

Myhill Nerode Theorem:

  • The language L accepted by a DFA is regular if and only if the number of equivalence classes of RL is finite.
  • The number of states in the smallest automaton accepting L is equal to the number equivalence classes in RL. Therefore, RL is of finite index.

Let ≡ (equivalence) on the states in M be such that

p ≡ q if and only if, for each input string x, δ(p, x) = δ(q, x) = qa

where qa is accepting state, then we say

⇒ p is equivalent to q or P is not distinguishable from q.

If δ(p, x) = qa and δ(q, x) = qn for some qa ∈ F and qn ∉ F then we say

⇒ p is distinguishable from q.

Algorithm for Finding Distinguishable States

  • For each pair [p, q] where p ∈ F and q ∈ {Q – F}, mark (p, q) = X
  • For each pair of distinct states [p, q] in F X F or (Q − F) X (Q − F) do
    • If for some input symbol a δ([p, q], a) = [r, s], if [r, s] = X then
    • Mark [p, q] = X
    • Recursively mark all unmarked pairs which lead to [p, q] on input for all a ∈ Σ.
    • Else
    • for all input symbols a do

      put [p, q] on the list for δ([p, q], a) unless δ([p, q], a) = [r, r]

Each unmarked pair [p, q] indicates the equivalent states.

Example 2.25

Find minimum-state automaton equivalent to the transition diagram given in Figure 2.41.

Fig 2.41    DFA

Solution: The distinguishable states are marked with symbol X. The relation among the states is represented as a matrix of size n × n. If p is distinguishable from q then q is also distinguishable to p and therefore, it is sufficient to have a lower matrix to represent the relation of one state to all other states.

Step 1: First mark for all states [p, q] where state p is final and q is non-final.

[d, a] = X
[d, b] = X
[d, c] = X
[d, e] = X
[d, f ] = X
[d, g] = X
[d, h] = X

Step 2: Find the states that are distinguishable from state a.

δ[a, b], 0) = [b, a]
δ[a, b], 1) = [a, c]
δ[a, c], 0) = [b, d]
δ[a, c], 1) = [a, b]
⇒mark[a, c] = X as [b, d] = X
⇒mark[a, b] = X as [a, c] = X
δ[a, e], 0) = [b, d]
δ[a, e], 1) = [a, f ]
⇒mark[a, e] = X as [b, d] = X
δ[a, f ], 0) = [b, g]
δ[a, f ], 1) = [a, e]
⇒mark[a, f ] = X as [a, e] = X
δ[a, g], 0) = [b, f ]
δ[a, g], 1) = [a, g]
δ[a, h], 0) = [b, g]
δ[a, h], 1) = [a, d]
⇒mark[a, h] = X as [a, d] = X

Find the states that are distinguishable from state b

δ[b, c], 0) = [a, d]
δ[b, c], 1) = [c, b]
⇒mark[b, c] = X as [a, d] = X
δ[b, e], 0) = [a, d]
δ[b, e], 1) = [c, f ]
⇒mark[b, e] = X as [a, d] = X
δ[b, f ], 0) = [a, g]
δ[b, f ], 1) = [c, e]
δ[b, g], 0) = [a, f ]
δ[b, g], 1) = [c, g]
⇒mark[b, g] = X as [a, f ] = X
δ[b, h], 0) = [a, g]
δ[b, h], 1) = [c, d]
⇒mark[b, h] = X as [c, d] = X

Find the states that are distinguishable from state c

δ[c, e], 0) = [d, d]
δ[c, e], 1) = [b, f ]
δ[c, f ], 0) = [d, g]
δ[c, f ], 1) = [b, e]
⇒mark[c, f ] = X as [d, g] = X
δ[c, g], 0) = [d, f ]
δ[c, g], 1) = [b, g]
⇒mark[c, g] = X as [d, f ] = X
δ[c, h], 0) = [d, g]
δ[c, h], 1) = [b, d]
⇒mark[c, h] = X as [d, g] = X

Find the states that are distinguishable from state e

δ[e, f ], 0) = [d, g]
δ[e, f ], 1) = [f, e]
⇒mark[e, f ] = X as [d, g] = X
δ[e, g], 0) = [d, f ]
δ[e, g], 1) = [f, g]
⇒mark[e, g] = X as [d, f ] = X
δ[e, h], 0) = [d, g]
δ[e, h], 1) = [f, d]
⇒mark[e, h] = X as [d, g] = X

Find the states that are distinguishable from state f

δ[f, g], 0) = [g, f ]
δ[f, g], 1) = [e, g]
⇒mark[f, g] = X as [e, g] = X
δ[f, h], 0) = [g, g]
δ[f, h], 1) = [e, d]
⇒mark[f, h] = X as [e, d] = X

Find the states that are distinguishable from state g

δ[g, h], 0) = [f, g]
δ[g, h], 1) = [g, d]
⇒mark[g, h] = X as [g, d] = X

Figure 2.42 shows the lower triangle with the entries computed.

Fig 2.42

From the lower triangle of the matrix it is clear that states [a, g], [b, f ] and [c, e] belong to same class. These states can be merged, and the minimized DFA is

a = 0
a = 1
→[a,g]
[b,f]
[a,g]
[b,f]
[a,g]
[c,e]
[c,e]
[d]
[b,f]
*[d]
[d]
[a,g]
[h]
[a,g]
[d]

2.9  Finite Automata with Output

The finite automaton designed so far gives outputs depicting whether the given strings are accepted or not. We can say that the output has only two possibilities, that is ‘yes or no’, But if it is required to have more than two outputs, we can associate the output with either state or transition. If the output is associated with state, the machine is called Moore machine (Figure 2.43(a)), and if the output is associated with transition, the machine is called as Mealy machine (Figure 2.43(b)).

Fig 2.43(a)    Moore Machine

Fig 2.43(b)    Mealy Machine

The Moore machine machine shown in Figure 2.43(a) gives the output as integer mod 3 for the input represented in binary form. For example, 5 in binary is 101, and the sequence taken on this input is q0, q1, q2, q2. Since it finally is in q2 state, the output generated at the end is 2, which is the output corresponding to q2 state.

The Mealy Machine in Figure 2.43(b) is designed to generate the output as ‘y’ if current input matches with the previous input, and to output ‘n’ if the input does not match for the input symbols on {a|b}*. For input abb, the final output would be ‘y’, and for input aba, the output would be ‘n’.

Note: Moore machine generates output for ɛ, and Mealy machine generates output only on some input symbol.

2.9.1  Moore Machine

Definition 6: A Moore machine is represented as a six-tuple M = {Q, Σ, Δ, δ, λ, q0} where

Q – Set of finite states.

Σ – Set of finite input symbols.

Δ – Set of finite output symbols.

δ – is a mapping function from Q X Σ to Q (i.e. Q X Σ → Q).

λ – is a mapping function which maps Q to Δ (i.e. Q → Δ).

q0 – is the initial state.

The state is associated with output. Whenever the Moore machine enters any state, it generates an output associated with that state. If the outputs are only two, then it can be viewed as a special case of finite automata.

2.9.2  Mealy Machine

Definition 7: A Mealy machine is represented as a six-tuple M = {Q, Σ, Δ, δ, λ, q0} where

Q – Set of finite states.

Σ – Set of finite input symbols.

Δ – Set of finite output symbols.

δ – is a mapping function from Q X Σ to Q (i.e. Q X Σ → Q).

λ – is a mapping function which maps Q X Σ to Δ (i.e. Q X Σ → Δ).

q0 – is the initial state.

The transition is associated with output. Whenever this machine enters any state on a particular input, it generates output.

Example 2.26

Design a Moore machine for inputs that are integer strings represented as binary, and give the output 0 for multiples of 2 and 1 for others.

Solution: Integer numbers, represented as binary, and their corresponding outputs are given below.

Integer number
Binary representation
Output
1
1
1
2
10
0
3
11
1
4
100
0
5
101
1
6
110
0
7
111
1

Let three states be defined by {I, q0, q1} where I is the initial state, q0 is a state associated with the output 0 and q1 is a state associated with 1. Add path in the automaton such that it enters the corresponding output state on the input sequence and the machine is shown Figure 2.44.

Fig 2.44

Example 2.27

Design a Melay machine to generate unary representatio for the given binary representation such that, the number of 0’s in unary is given as Nu(0) = Nb(0) + 2 * Nb(1) if it starts with 1, otherwise Nu(0) = 2 * Nb(0) + Nb(1).

Solution: The Mealy machine requires three states. In the first state (I) on input 0, it changes to state q0 indicating that input starts with 0, and on 1 input moves to state q1 indicating that input starts with 1. In q0 for input 0, it generates output 00, and for input 1, it generates output 0. Similarly in q1 state, for input 0, it generates output 0, and for input 1, it generates output 00. A Mealy machine is shown in Figure 2.45.

Fig 2.45

2.9.3  Equivalence Between Moore and Mealy Machines

Theorem 2: If M1 = {Q, Σ, Δ, δ, λ, q0} is a Moore machine, then there is a Mealy machine M2 equivalent to M1.

Proof: Let M2 = {Q, Σ, Δ, δ, λ`, q0} be a Mealy machine where λ` is defined by

λ`(q, a) = λ(δ(q, a)) for all q in Q and a in Σ.

If there is any input x processed in M1 that generates a sequence of states q1, q2, ….. qn then the same sequence would be generated in M2.

With each transition, M2 emits the output that M1 associates with the state entered.

Theorem 3: If M1 = {Q, Σ, Δ, δ, λ, q0} is a Mealy machine, then there is a Moore machine M2 equivalent to M1.

Proof: Let M2 = {{Q × Δ}, Σ, Δ, δ`, λ`, [q0, b0]}where b0 is an arbitrarily selected member of Δ. Let the states in M2 be pairs [q, b] where q ∈Q and b∈Δ.

 

Let δ` be defined by δ`([q, b], a) = [δ(q, a), λ(q, a)].

Let λ` be defined by λ`([q, b]) = b.

Using induction it can be shown that M2 can simulate all the moves of M1 i.e if M1 enter states sequence as q0, q1, q2, ….. qn on input a1, a2, a3 …… an and emits output b1, b2, …… bn, then M2 enters states [q0, b0], [q1, b1], [q2, b2]…… [qn, bn] and emits outputs b0, b1, b2, …..bn.

2.9.4  Interconversions Between Machines

Example 2.28

Construct a Moore machine for the following Mealy machine.

Solution:

  1. Frame the possible states of the form [q a] where q ∈Q and a ∈Δ. The number of states generated would be n × m where n is the number of states in Q and m is the number of output symbols, and out of these states, only few would be necessary. To include only the required ones, first identify the state qi which is associated with different outputs.
  2. Represent of qi as different states, such that the number of states is equal to the number of different outputs associated with qi.
  3. Reconstruct the table with new states.
  4. Construct its equivalent Mealy machine.
  5. If the initial state is associated with output then create a new state and add the transitions similar to initial state q1 and add the output as ɛ.

Step 1: In the given table, q1 and q3 are associated with only one output. But q2 and q4 are associated with two different outputs.

Step 2: Represent q2 as two states as q20 and q21, represent q4 as two states q40 and q41.

Step 3: Reconstruct the table with new states.

Step 4: Construction of equivalent Moore machine.

Step 5: Since q1 state is associated with output 1 add a new initial state q0 and associate with it the transitions of q1, but with output ɛ.

Example 2.29

Construct the Mealy machine for the given Moore machine.

Solution:

We construct the Mealy machine by associating the output with transition. The resultant table is

We observe that the transitions corresponding to q2 state and q3 state are same. Hence, we can eliminate q3 state and modify the Mealy machine to

2.10  Applications of Finite Automata with Output

Moore machines are useful to describe language recognizers, to describe counters, such as a modulo-4 counter. Mealy machines are useful to describe DFA in which an output is associated with the transition. A full-adder changes the states to reflect the carry-in, and it outputs the sum as the transition takes place.

2.10.1  The Full-adder

Moore machine: Here we use the carry-in as the state. The DFA will output the sum, but this example will ignore that and focus on the state transitions.

Note that a two-state Moore machine does not easily display the sum.

A complete Moore machine model of a full-adder would require four states.

q0
Carry-In = 0
Sum = 0
q1
Carry-In = 0
Sum = 1
q2
Carry-In = 1
Sum = 0
q3
Carry-In = 1
Sum = 1

Mealy machine:

To simplify the definition, let Q = {q0, q1}, where

q0 is the state previously labelled as ‘Carry-In = 0’ and

q1 is the state previously labelled as ‘Carry-In = 1’.

The input alphabet is Σ = {<0, 0>, <0, 1>, <1, 0>, <1, 1>}.

Please note that this alphabet has four symbols.

The output alphabet is Δ = {0, 1}.

The transition function:
δ(q0, <0, 0>) = q0
δ(q1, <0, 0>) = q0
δ(q0, <0, 1>) = q0
δ(q1, <0, 1>) = q1
δ(q0, <1, 0>) = q0
δ(q1, <1, 0>) = q1
δ(q0, <1, 1>) = q1
δ(q1, <1, 1>) = q1
The output function:
λ(q0, <0, 0>) = 0
λ (q1, <0, 0>) = 1
λ (q0, <0, 1>) = 1
λ (q1, <0, 1>) = 0
λ (q0, <1, 0>) = 1
λ (q1, <1, 0>) = 0
λ (q0, <1, 1>) = 0
λ (q1, <1, 1>) = 1

Fig 2.46

Fig 2.47

2.10.2  The String Sequence Detector

We now investigate two implementations of a 11011 sequence detector.

Each of these machines accepts strings, one symbol at a time.

The alphabet for each machine is Σ = {0, 1}.

Each machine will accept any string with a five-symbol suffix 11011.

Moore machine: Let Q = {q1, q2, q3, q4, q5, q6} where q1 is the start state, Σ = {0, 1} F = {q6}

The transition function is given by the following equations.

δ(q1, 0) = q1, δ(q2, 0) = q1, δ(q3, 0) = q4, δ(q4, 0) = q1, δ(q5, 0) = q1, δ(q6, 0) = q1
δ(q1, 1) = q2, δ(q2, 1) = q3, δ(q3, 1) = q3, δ(q4, 1) = q5, δ(q5, 1) = q6, δ(q6, 1) = q2

Fig 2.48

Mealy machine: Here the input and output alphabets are considered same.

Q = {q1, q2, q3, q4, q5} where q1 is the start state

Σ = {0, 1}

Δ = {0, 1}

Fig 2.49

The transition function is given by the following:

  1. δ(q1, 0) = q1, δ(q2, 0) = q1, δ(q3, 0) = q4, δ(q4, 0) = q1, δ(q5, 0) = q1,
    δ(q1, 1) = q2, δ(q2, 1) = q3, δ(q3, 1) = q3, δ(q4, 1) = q5, δ(q5, 1) = q1.

    The output function is given by the following:

  2. l (q1, 0) = 0, λ (q2, 0) = 0, λ (q3, 0) = 0, λ (q4, 0) = 0, λ (q5, 0) = 0,
    λ (q1, 1) = 0, λ (q2, 1) = 0, λ (q3, 1) = 0, λ (q4, 1) = 0, λ (q5, 1) = 1.

Solved Problems

Problem 1: Consider a toy game shown in Figure 2.50. A marble is dropped in at A or B. Levers X1, X2, X3 cause the marble to fall either to the left or right. Whenever a marble encounters a lever, marble causes the lever to change state, so that the next marble to encounter the lever will take the opposite branch.

Model this toy by an FA. Denote marble input at A by input 0 and a marble input at B by input 1. A sequence of inputs is accepted if the last marble comes out at D. Describe the set accepted by FA.

Fig 2.50

Solution: This problem can be modelled using finite automata in which each lever has two possible moves, that is, L for left and R for right. We assume that 0 indicates the marble is dropped from A and 1 indicates that the marble is dropped from B. Initially in the start state, it is assumed that all levers are towards left, indicated by state LLL (for positions of X1, X2 and X3, respectively). If the marble is dropped from A only X1 would change from L to R and if the marble is dropped from B then the lever X2, X3 would change to R. The change of lever states is shown in the following table.

Note: Marble coming out of D wins the game.

Set of accepting states are * marked.

X1 X2 X3
0
1
→LLL
RLLC
LRRC
RLLC
LLRC
RRRC
LRRC
RRRC
RLRD*
LRLC
RRLC
LLLD*
RRRC
LRLD*
RLRD*
LLRD*
RLRC
LRLD*
RLRD*
LRRC
RLLD*
LLLD*
RLLC
LRRC
LRLD*
RRLC
LLLD*
RRLD*
LRRD*
RLLD*
RLRD
LLLD*
RRLD*
RLRC
LLLD*
RRLD*
RLLD*
LLRC
RRLD*
LRRD*
RRRC
LLRD*
LLRC
RLRC
LRLD*

Problem 2: Design an FA that accepts strings in L such that integer number ‘a’ when represented in binary form is divisible by 3.

Solution: It is required to construct a DFA such that any integer in binary form that is divisible by 3 should enter into final state on seeing the last digit.

When we divide any number by 3, there are three possible remainders 0, 1 or 2. So, it is required to have three states to indicate each possibility. So, let

q0 - represent remainder 0

q1 - represent remainder 1

q2 - represent remainder 2. The states are shown in the Figure 2.51

Fig 2.51

Since the number should be divisible by 3, which gives the remainder as zero, the state q0 is made as final state.

Problem 3: Design DFA that accepts all strings with 0’s and 1’s such that any five consecutive symbols have at least two 0’s.

Solution: This problem can be solved by keeping track of the previous four symbols and the current symbol. We make an assumption that the string would have at least a length of five symbols to be accepted. This requires many states shown below. We use a special state D to indicate a dummy state. The minimum length of string is assumed to be of length 5.

Note: The suffix of every state keeps track of the sequence of symbols seen so far.

State ↓Input →
a=0
a=1
→ S
q0
q1
q0
q00
q01
q1
q10
q11
q00
q000
q001
q01
q010
q011
q10
q100
q101
q11
q110
q111
q000
q0000
q0001
q001
q0010
q0011
q010
q0100
q0101
q011
q0110
q0111
q100
q1000
q1001
q101
q1010
q1011
q110
q1100
q1101
q111
q1110
D
q0000
q00000
q00001
q0001
q00010
q00011
q0010
q00100
q00101
q0011
q00110
q00111
q0100
q01000
q01001
q0101
q01010
q01011
q0110
q01100
q01101
q0111
q01110
D
q1000
q10000
q10001
q1001
q10010
q10011
q1010
q10100
q10101
q1011
q10110
D
q1100
q11000
q11001
q1101
q11010
D
q1110
q11100
D
D
D
D
*q00000
q00000
q00001
*q00001
q00010
q00011
*q00010
q00100
q00101
*q00011
q00110
q00111
*q00100
q01000
q01001
*q00101
q01010
q01011
*q00110
q01100
q01101
*q00111
q01110
D
*q01000
q10000
q10001
*q01001
q10010
q10011
*q01010
q10100
q10101
*q01011
q10110
D
*q01100
q11000
q11001
*q01101
q11010
D
*q01110
q11100
D
*q10000
q00000
q00001
*q10001
q00010
q00011
*q10010
q00100
q00101
*q10011
q00110
q00111
*q10100
q01000
q01001
*q10101
q01010
q01011
*q10110
q01100
q01101
*q11000
q10000
q10001
*q11001
q10010
q10011
*q11010
q10100
q10101
*q11100
q11000
q11001

Problem 4: Design a DFA that accepts the set of all strings beginning with 1 (which, interpreted as binary representation of an integer, is congruent to zero modulo 5).

Solution: Possible outputs with modulo 5 operation are 0, 1, 2, 3, 4. Let these states be denoted by q0 q1 q2 q3 q4 (representing remainders 0, 1, 2, 3, 4, respectively). It is also said that the string should begin with 1. If the string starts with 0 it should not be accepted. Hence, 0 is not a valid integer in the set. So on seeing 0, it should enter into a dummy state. Add a new initial state S and a dummy state qd. Figure 2.52 shows the designed DFA.

Fig 2.52    DFA for Integer Mod 5

Problem 5: Design a DFA to accept strings having 111 as substring.

Solution: The language has strings which are of the form {111, 0111, 1111, 1110, 00111, 01111, 10111, 11111,………….}. The DFA should have four states. In the 0th state, if it finds 1, it changes to 1st state. In 1st state if it finds 1, it changes to 2nd state. In 2nd state if it finds 1, it changes to 3rd state. Declare 3rd state as final and be in the same state on 0 or 1. In states other than the 3rd, if it finds 0, it should start from initial state as there would not be 111’s. The DFA is shown in Figure 2.53.

Fig 2.53    DFA for Problem 5

Problem 6: Design DFA for L(M) = {anb | n ≥ 0}

Solution: Start with initial state q0. Define an by taking loop. To have b next, have another state q1.The transitions on q1 can be defined to move on to dummy state q2.

Fig 2.54    DFA for Strings with a’s Followed by a b

Problem 7: Design DFA to accept set of all strings ending in 00.

Solution: The language has strings which are of the form {00, 100, 000, 0000, 1000, 0100, 1100, ……}. The DFA should have three states. In the 0th state, if it finds 0, it changes to 1st state. In 1st state if it finds 0, it changes to 2nd state. Declare 2nd state as final and be in the same state on 0. In any state, if it finds 1, it should change to initial state as it should end with 00. The DFA is shown Figure 2.55.

Fig 2.55    DFA for Strings Ending with 00

Problem 8: Design DFA to accept the set of all strings not containing 101 as substring.

Solution: The language has strings of the form {e, 0, 1, 00, 10, 01, 11, 001,.}. It should not contain strings that have 101 as substring. First define DFA with four states with 101 string. Declare the last state q3 as dead state. The remaining states can be declared as final states as it has to accept strings of length 0, 1, 2,…. The moves on each state are defined as shown in Figure 2.56.

Fig 2.56    DFA for String with Substring 101

Problem 9: If L(M) = {0m 1n | m, n ≥ 0}, design DFA for M.

Solution: Strings of the form {ɛ, 0, 1, 00, 01, 11, 000, 001, 011, 111, 0000, 0001, 0011, 0111, 1111,….} are valid in the language. Since ɛ is valid, initial state is declared as final state. It stays in the same state q0 on 0’s and changes to q1 on 1. Declare q1 as final state.

Be in q1 state on 1 and move to dead state q2 on 0. Be in this same state whether on 0 or on 1, as they are invalid strings.

Fig 2.57    DFA for Strings with 0’s Followed by 1’s

Problem 10: Design DFA to accept the set of all strings containing three consecutive 0’s.

Solution: The language has strings of the form {000, 1000, 0000, 0001, 11000, 10000, 01000, 00000,………….}. The DFA should have four states. In the 0th state, if it finds 0, it changes to 1st state. In 1st state, if it finds 0, it changes to 2nd state. In 2nd state, if it finds 0, change to 3rd state. Declare 3rd state as final and be in the same state on 1 or 0. In states other than the3rd, if it finds 1, it should start from initial state as there would not be 000’s. The DFA is shown in Figure 2.58.

Fig 2.58    DFA for Strings with Three Consecutive 0’s

Problem 11: Design DFA that accepts even number of a’s or even number of b’s.

Solution: The language has strings which are of the form {aa, bb, abb, bab, bba, aab, aba, aab,….}. The DFA should have four states. q0 indicates the condition where number of a’s and b’s are even. q2 indicates the condition where number of a’s is even and number of b’s is odd. q1 indicates that number of b’s is even and number of a’s is odd, and q4 indicates that number of a’s is odd and, further, number of b’s is also odd. The DFA is shown in

Fig 2.59    DFA for Even Number of a’s or b’s

Problem 12: Design the NFA that accepts 1100 only.

Solution: The NFA for the given condition can be drawn in many ways. Samples are shown in Figure 2.60.

Fig. 2.60  DFA for String 1100

Problem 13: Design the NFA that accepts strings that contains either two consecutive 0’s or two consecutive 1’s.

Solution: The language has strings of the form {00, 11, 000, 100, 001, 110, 011, 111…}

Therefore, whether on two consecutive 0’s or 1’s, go to state q3 using q1 or q2. In q0 and q3 states, define moves to be in the same state on 0/1 as shown in Figure 2.61.

 

Fig. 2.61  DFA for 00 or 11

Problem 14: Design the NFA to accept (a) all strings containing 1100 as substring or (b) the set of all strings in which a pair of 1’s is followed by a pair of 0’s.

Solution:

Fig. 2.62  NFA for Substring 1100

DFA is difficult to construct, but it is fast in processing strings. NFA is easy to construct, but it is slow in processing. Hence, it is always desirable to construct the NFA and convert it to a DFA, as for every NFA that accepts L three exists an equivalent DFA that accepts the same L and is shown in Figure 2.62.

Problem 15: Convert the following NFA to DFA.

δ
0
1
→p
{pq}
p
q
r
r
r
s
-
*s
s
s

Solution: Start with initial state: find transitions. Whenever you get new set of states, add it to set of states and find transitions on input symbols.

δ
0
1
→[p]
[pq]
[p]
[pq]
[pqr]
[pr]
[pr]
[pqs]
[p]
[pqr]
[pqrs]
[pr]
*[pqs]
[pqrs]
[prs ]
*[pqrs]
[pqrs]
[prs ]
*[prs]
[pqs]
[ps]
*[ps]
[pqs]
[ps]

Problem 16: Design NFA for language L(M) = 01*0*1.

Solution: The strings are of the form: 0 followed by zero or more 1’s, followed by zero or more 0’s but ending with 1.

Fig. 2.63  NFA for Problem 16

Problem 17: Design NFA for language L(M) = 01* | 0*1.

Solution: The language has strings {0, 01, 011, 0111 …..} ∪ {1, 01, 001, 0001,….}.

This can be drawn in two ways as shown in Figure 2.64:

Fig. 2.64  Two Possible Ways of Drawing NFA for 10* / 0*1

Problem 18: Find whether the following two are equivalent or not.

Fig. 2.65

Solution: Equivalence of two automata (i.e. if they accept same language):

  1. Two FAs over ∑ are equivalent if they accept the same set of strings over ∑.
  2. When two FAs are not equivalent, there exists some string w over ∑ for which, one automaton reaches a final state on w whereas the other reaches a non-final state.

we can simplfy DFA in Figure 2.65(a) by removing state q5 as it is not reachable.

Current State (M1, M2)
Next state (M1, M2)
0
1
→(q0, q1 1)
(q1, q2 1)
(q3, q2 1)
(q1, q2 1)
(q3, q2 1)
(q2, q3 1)
(q3, q2 1)
(q3, q2 1)
(q4, q3 1)
(q2, q3 1)
(q2, q3 1)
(q2, q3 1)
(q4, q3 1)
(q4, q3 1)
(q4, q3 1)

It is observed that for all pairs (p, q), where p ∈ states in Figure 2.65(a) and q ∈ states in Figure 2.65(b), they both either go to non-final state or final state. Hence, these two are said to be equivalent.

We can simplify state q5 not reachable.

Problem 19: Reduce the DFA shown in Figure 2.66.

0
1
→1
2
3
2
4
5
3
6
7
4
4
5
5
6
7
*6
4
5
7
6
7

Fig. 2.66

Here in this problem equivalent classes are named using alphabets A, B, C ...

Solution:

0 {A, B} = {{6}, {1, 2, 3, 4, 5, 7}}

1 {A, C, D} = {{6}, {1, 2, 4}, {3, 5, 7}}

1 {A, C, D} = {{6}, {1, 2, 4}, {3, 5, 7}}

 
0
1
→{1, 2, 4}
{1, 2, 4}
{3, 5, 7}
{3, 5, 7}
{6}
{3, 57}
*{6}
{1, 2, 4}
{3, 5, 7}

Fig. 2.67

The language accepted by this DFA is set of all strings of 0's and 1' is that end with 10.

Problem 20: Minimize the DFA shown in Figure 2.68.

a
b
→ Q0
Q1
Q0
Q1
Q0
Q2
Q2
Q3
Q1
*Q3
Q3
Q0
Q4
Q3
Q5
Q5
Q6
Q4
Q6
Q5
Q6
Q7
Q6
Q3

Fig. 2.68

Solution:

0 {1, 2} = {q3} {q0 q1 q2 q4 q5 q6 q7}

1 {1, 3, 4, 5} = {q3} {q0 q1 q5 q6} {q2 q4} {q7}

2 {1, 4, 6, 7} = {q3} {q0 q6}{q2 q4} {q1 q5} {q7}

3 {1, 4, 6,7} = {q3} {q0 q6} {q2 q4} {q1 q5} {q7}

a
b
→Q0,6
Q1,5
Q0,6
Q1,5
Q0,6
Q2,4
Q2,4
Q3
Q1,5
*Q3
Q3
Q0,6

Fig. 2.69

Note: If the DFA in Figure 2.68 is observed carefully, it is clear that the states Q4, Q5, Q6 and Q7 are not reachable from Q0 state they can be eliminated directly.

Problem 21: Minimize the finite automata given in Figure 2.70.

Fig. 2.70

Solution: Let us represent the DFA as a transition table.

a = a
a = b
→q0
q3
q5
q1
q0
q6
q2
q1
q3
q3
q5
q4
q4
q6
q4
*q5
q2
q5
*q6
q2
q6
  1. Initially we identify 0-equivalence as ∏0 = {Q10, Q20} where Q10 is set of final states and Q20 = Q − Q10 is set of non-final states.

    Q10 = {q5, q6}

    Q20 = {q0, q1, q2, q3, q4}

  2. Construct ∏1 from ∏0 identifying the equivalent states in {Q10, Q20}.

    Q10 has two states and Q20 has five states, and we need to identify whether they are 1-equivalent.

    Compare q5, q6 on inputs a and b.

    both resultant states belong to Q20.
    both both resultant states belong to Q10.

    ⇒ q5 is 1-equivalent to q6 hence Q10 cannot be divided.

    Compare q0, q1 on inputs a and b.

    both resultant states belong to Q20.
    both resultant states belong to Q10.

    ⇒ q0 is 1-equivalent to q1.

    Compare q0, q2 on inputs a and b.

    both resultant states belong to Q20.
    these two states belong to different sets in ∏0.

    ⇒ q0 is not 1-equivalent to q2. Hence Q20 is split into two sets.

    Compare q0, q3 on inputs a and b.

    these two states belong to different sets in ∏o
    these two states belong to different sets in ∏o

    ⇒ q0 is not 1-equivalent to q3

    Compare q0, q4 on input a and b.

    these two states belong to different sets in ∏o
    these two states belong to different sets in ∏o

    ⇒ q0 is not 1-equivalent to q4

    Therefore, ∏1 = {Q11, Q21, Q31}

    where

    Q11 = {q5, q6}

    Q21 = {q0, q1}

    Q31 = {q2, q3, q4}

  3. Construct ∏2 from ∏1, identifying the equivalent states in {Q11, Q21, Q31}.

    Q11 and Q21 have two states, and Q31 has three states. We need to identify whether they are 2-equivalent.

    Compare q5, q6 on inputs a and b.

    both resultant states belong to Q31.
    both resultant states belong to Q11.

    ⇒ q5 is 2-equivalent to q6,Hence Q11 cannot be divided.

    Compare q0, q1 on inputs a and b.

    these two states belong to different sets in ∏1
    both resultant states belong to Q11.

    ⇒ q0 is not 2-equivalent to q1

    Compare q2, q3 on inputs a and b.

    these two states belong to different sets in ∏1
    both resultant states belong to Q31.

    ⇒ q2 is not 2-equivalent to q3.

    Compare q2, q4 on inputs a and b.

    these two states belong to different sets in ∏1
    both resultant states belong to Q31.

    ⇒ q2 is not 2-equivalent to q4.

    Therefore, ∏2 = {Q12, Q22, Q32, Q42, Q52},

    where

    Q12 = {q5, q6}

    Q22 = {q0}

    Q32 = {q1}

    Q42 = {q2}

    Q52 = {q3, q4}

  4. Construct ∏3 from ∏2, identifying the equivalent states in {Q12, Q22, Q32, Q42, Q52}.

    Q12, Q52 have only a single state. Hence, these sets cannot be divided.Q12 and Q52 have two states; we need to identify whether they are 3-equivalent.

    Compare q5, q6 on inputs a and b.

    both resultant states belong to Q42.
    both resultant states belong to Q12.

    ⇒ q5 is 3-equivalent to q6 Q11 cannot be divided.

    Compare q3, q4 on inputs a and b.

    both resultant states belong to Q12.
    δ(q3, b) = q4
    δ(q4, b) = q4.

    ⇒ q3 is 3-equivalent to q4

    Therefore, ∏3 = {Q13, Q23, Q33, Q43, Q53},

    where

    Q11 = {q5, q6}

    Q21 = {q0}

    Q31 = {q1}

    Q41 = {q2}

    Q51 = {q3, q4}

  5. We see that ∏3 is equal to ∏2. The states q5 and q6 are considered as the single state q56, and q3 and q4 are considered as the single state q34. Minimized DFA is
    a = a
    a = b
    →q0
    q34
    q56
    q1
    q0
    q56
    q2
    q1
    q34
    q34
    q56
    q34
    *q56
    q2
    q65

Problem 22: Construct Moore machine for the following Mealy machine (Figure 2.71).

Fig. 2.71

Solution:

In the given table, all states are associated with only one output. No state needs to be split as all states are with one output.

Equivalent Moore Machine

Problem 23: Give Mealy and Moore machine for input from (0+1)* satisfying the given condition. If input ends with 101, output is A if input ends with 110, output is B; otherwise output is C.

Solution: For this problem, it is easy to construct Moore machine and then convert it into its equivalent Mealy machine.

Fig. 2.72

Its corresponding Mealy machine is as follows.

Problem 24: Give Mealy and Moore machines for input from (0 + 1 + 2)* to print the residue modulo 5 of the input treated as a ternary (base 3, with digits 0, 1, 2) numbers.

Solution: To construct the Moore machine we have to understand the possible outputs. Since it is residue modulo 5, the possible outputs are 0, 1, 2, 3 and 4. The possible inputs would be the ternary representations of the integers.

Example:

Integer number
Ternary representation
Output
1
1
1
2
2
2
3
10
3
4
11
4
5
12
0
6
20
1
7
21
2
8
22
3
9
100
4
10
101
0
11
102
1
12
110
2
13
111
3
14
112
4

The Moore machine is given in Figure 2.73.

Fig. 2.73

The corresponding Mealy machine is

Problem 25: Draw a DFA to accept strings with a’s and b’s such that the number of a’s is a multiple of 3 and the number of b’s is a multiple of 2.

Solution: To construct a DFA satisfying both conditions, first let us construct DFAs independent of each condition and then merge them to get the final DFA.

  1. a’s in multiples of 3 (Figure 2.74):

    Fig. 2.74

  2. b’s in multiples of 2 (Figure 2.75):

    Fig. 2.75

To construct a DFA satisfying both the conditions, merge the two DFAs.

The states in the final DFA are {[AX], [AY], [AZ], [BX], [BY], [BZ], [CX], [CY], [CZ], [DX], [DY], [DZ]}

The state which satisfies both the conditions is [DZ]. To find the transitions of the DFA, start at the initial state [AX]. The transitions are defined as follows:

δ([PQ], a) = [ δ(P, a) δ(Q, a)] where P is a state of the 1st DFA and Q is a state of the 2nd DFA.

i = a 
i = b
→[AX]
[BX]
[AY]
[AY]
[BY]
[AZ]
[AZ]
[BZ]
[AY]
[BX]
[CX]
[BY]
[BY]
[CY]
[BZ]
[BZ]
[CZ]
[BY]
[CX]
[DX]
[CY]
[CY]
[DY]
[CZ]
[CZ]
[DZ]
[CY]
[DX]
[BX]
[DY]
[DY]
[BY]
[DZ]
*[DZ]
[BZ]
[DY]

Fig. 2.76

Problem 26: Construct the DFA for the following NFA with ɛ moves:

Solution:

Step 1: Compute ɛ-closure of each state.

(q0) = {q0, q1, q2}
(q1) = {q1}
(q2) = {q2}
(q3) = {q3}
(q4) = {q4}

Step 2: Explore the valid states in DFA that are computed in step 2.

(q0, 0) = ε-closure (δ(ε-closure (q0), 0))
= ε-closure (δ({q0, q1, q2}, 0))
= ε-closure ({∅}, ∪ {q4}, ∪{q2})
= [q2 q4 ]
(q0, 1) = ε-closure (δ(ε-closure (q0), 1))
= ε-closure (δ({q0, q1, q2},1))
= ε-closure ({∅}, ∪{∅}, ∪{q3})
= [q3]
([q2 q4], 0) = ε-closure (δ(ε-closure ([q2 q4]), 0))
= ε-closure (δ({q2, q4}, 0))
= ε-closure ({q2}, ∪{∅})
= [q2]
([q2 q4], 1) = ε-closure (δ(ε-closure ([q2 q4]), 1))
= ε-closure (δ({q2, q4}, 1))
= ε-closure ({q3}, ∪{q4})
= [q3 q4]
([q3], 0) = ε-closure (δ(ε-closure ([q3]), 0))
= ε-closure (δ({q3}, 0))
= ε-closure ({∅})
= [∅]
 ([q3], 1) = ε-closure (δ(ε-closure ([q3]), 1))
= ε-closure (δ({q3}, 1))
= ε-closure ({∅})
= [∅]
([q2], 0) = ε-closure (δ(ε-closure ([q2]), 0))
= ε-closure (δ({q2},0))
= ε-closure ({q2})
= [q2]
([q2], 1) = ε-closure (δ(ε-closure ([q1]), 1))
= ε-closure (δ({q2},1))
= ε-closure ({q3})
= [q3]
([q3, q4], 0) = ε-closure (δ(ε-closure ([q3,q4]), 0))
= ε-closure (δ({q3}, 0) ∪ δ({q4}, 0))
= ε-closure ({∅ ∪ ∅})
= [∅]
([q3, q4], 1) = ε-closure (δ(ε-closure ([q3, q4]), 1))
= ε-closure (δ({q3}, 1)∪ δ→({q4}, 1))
= ε-closure ({∅ ∪ q4})
= [q4]
([q4], 0) = ε-closure (δ(ε-closure (δ(q4, 0)))
= ∅
 ([q4], 1) = ε-closure (δ(ε-closure (δ(q4, 1)))
= [q4]

Similarly, we compute for every new state that appears, and the computed values are used to get the following table:

a = 0
a = 1

→ɛ*(q0)

=* [q0 q1 q2]

[q2 q4]
[q3]

*[q2 q4]

[q2]
[q3 q4]

* [q3]

[∅]
[∅]

[q2]

[q2]
[q3]

[*[q3 q4]

[∅]
[q4]

[q4]

[∅]
[q4]

[∅]

[∅]
[∅]

Transition diagram for DFA is shown in the following figure:

Problem 27: Convert the following NFA with ɛ to DFA.

Solution:

Step 1: Compute ɛ-closure of each state.

(A) = {A, B, D}
(B) = {B}
(C) = {C}
(D) = {D}
(E) = {E}

Step 2: Explore the valid states in DFA that are computed in step 2.

i/p = a
i/p = b
→ɛ*(A)
[ABCDE]
[DE]
=[ABD]
[ABCDE]
[ABCDE]
[BDE]
[DE]
[E]
[D]
[BDE]
[CE]
[DE]
[E]
[Ø]
[Ø]
[D]
[E]
[D]
[CE]
[Ø]
[B]
[Ø]
[Ø]
[Ø]
[B]
[C]
[E]
[C]
[Ø]
[B]

Transition diagram for DFA is shown in the following figure:

Summary

  1. Finite Automata can be represented as a 5-tuple, transition table or transition diagram.
  2. FA can be used as language acceptor.
  3. For every NFA with ɛ, we can construct a NFA without ɛ.
  4. We can construct equivalent DFA for any NFA.
  5. Two finite automata are said to equivalent if the language accepted by the two machines is same.
  6. Number of states in FA can be minimized by Myhill Nerode theorem or by π constructions method.
  7. Moore and Mealy machines are the special finite-state machines with output.
  8. In Moore machine, output is associated with state.
  9. In Mealy machine, output is associated with state and input.

Short Answers

  1. What is a finite automaton? Give two examples.

    Answer: Finite automaton is a mathematical model of a system consisting of finite set of state, set of transition from state to state that occurs on input symbols from alphabet.

    Examples: Text editorand lexical analyser are examples.

  2. Enumerate the differences between NFA and DFA.

    Answer: DFA has moves well-defined on the current state and current input symbol. In NFA, the moves are not well defined. In NFA, multiple moves are defined either on ɛ or single input symbol.

  3. List any four ways of theorem proving. (Nov 2007)

    Answer: The four ways of theorem proving are

    1. Proof by induction
    2. Proof by contradiction
    3. Proof by transposition
    4. Proof by construction
  4. What is meant by equivalent states in DFA? (Nov 2007)

    Answer: Definitions 4 and 5 of Section 1.8.2.

  5. Define automata.

    Answer: Definition 1 of Section 1.2.

  6. What is the principle of mathematical induction?

    Answer: See Section 1.1

  7. Construct a DFA, over Σ = {a, b}, that produces not more than 3 a’s.

    Answer: See Example 14.

  8. Define the languages accepted by NFA and DFA

    Answer: Language of DFA A = {Q, ∑, δ, q0, F}is defined by

     

    {w | δ`(q0, w) = P for some P in F}

    Language of NFA A = {Q, ∑, δ, q0, F}is defined by

    {w | δ`(q0, w) ∩ F ≠ ∅}; that is, there is at least one final state in the resultant set.

Fill in the Blanks

  1. The number of states in DFA is _______________ than the number of states in NFA for the same language.
  2. The transition function for NFA is a mapping function given as _____________.
  3. The transition function for DFA is a mapping function given as ______________.
  4. The finite automata to recognize n words each of maximum length m require ____________ states.
  5. The time required to process a string of length x by NFA with N states is __________ compared to the time required by a DFA for the same language.
  6. The minimum number of states required to accept the language L = {w/w ∈ (a + b)*} is _____________ .
  7. The minimum number of states required to accept the language L = {xay/x, y∈ (a + b)*} is _____________ .
  8. Finite automata for accepting words ‘this’ and ‘that’ require _______ states.
  9. ________________ of a state is the set of states that can be reached by e-transitions.
  10. NFA with ɛ can increase the processing time of NFA (True/False).
  11. Elimination of ɛ-edges from NFA increases___________.
  12. The two states q1 and q2 are said to be _________ if both δ (q1, a) and (q2,a) reach final states or both of them reach non-final states for all a ∈ ∑.
  13. The output in ________________ machine is associated with transition.
  14. All Moore machines have an equivalent finite automata (True/False).
  15. For every finite automaton, there is always an equivalent Moore and Mealy machines (True/False).

Answers

  1. greater.
  2. Q × Σ to 2Q
  3. Q × Σ to Q
  4. 2mn
  5. less
  6. one
  7. two
  8. seven
  9. epsilon closure
  10. true
  11. number of edges
  12. equivalent
  13. Melay
  14. False
  15. True

Objective Question Bank

  1. FA has
    1. Unlimited memory
    2. No memory at all
    3. Limited Memory
    4. none of the above
  2. Consider the following deterministic finite-state automaton M:

    Let S denote the set of four-bit binary strings in which the first is 0 and fourth is 0. Find the number of strings in S that are accepted by M. It is

    1. 2
    2. 5
    3. 7
    4. 8
  3. How many two-state FAs can be drawn over the alphabet {0, 1} to accept an empty language ?
    1. 12
    2. 14
    3. 20
    4. 15
  4. How many two-state FAs can be drawn over the alphabet {0, 1} to acept the language (0+1)*
    1. 12
    2. 14
    3. 20
    4. 15
  5. The smallest FA that accepts the language {x/length of x is divisible by 3} has
    1. 2 states
    2. 3states
    3. 4 states
    4. 5 states
  6. How many DFAs exist with two states over the input alphabet (a, b)?
    1. 16
    2. 26
    3. 32
    4. 64
  7. How many DFAs exist with three states over the input alphabet {0, 1}?
    1. 144
    2. 6561
    3. 5832
    4. 729
  8. The recognizing capabilities of NDFSM and DFSM
    1. may be different
    2. must be different
    3. must be same
    4. none of the above
  9. What is the minimum number of states of the NFA that accepts the language {ababn | n≥0} U {aban | n ≥ 0}?
    1. 4
    2. 3
    3. 5
    4. 9
  10. What is the minimum number of states in the NFA accepting the language{ab, abc}?
    1. 4
    2. 5
    3. 3
    4. 2
  11. Consider the NFA M shown below:

    Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1 obtained by changing non-accepting states of M to accepting states. Which of the following statements is true?

    1. L1 = {0, 1)* – L
    2. L1 = {0, 1}*
    3. L1 ≠ L
    4. L1 = L
  12. The basic limitation of FSM is that
    1. It cannot remember arbitrarily large amount of information.
    2. It sometimes recognizes grammars that are not regular.
    3. It sometimes fails to recognize grammars that are regular.
    4. All of the above comments are true.
  13. Given an arbitrary NFA with N states, the maximum number of states in an equivalent minimized DFA is at least
    1. N2
    2. N
    3. 2N
    4. N!
  14. The FSM pictured below recognized
    1. all strings
    2. no string
    3. ɛ alone
    4. None of the above
  15. The number of states of the FSM required to simulate the behaviour of a computer, with a memory capable of storing ‘m’ words, each of length ‘n’ bits, is
    1. m × 2n
    2. 2mn
    3. 2m + n
    4. None of the above.
  16. Consider the following 2-DFA ({q0, q1, q2, q3, q4}, {0, 1}, δ q0, {q2}), where δ is
    0
    1
    →q0
    q0, R
    q1, R
    q1
    q1, R
    q2, R
    * q2
    q2, R
    q3, L
    q3
    q4, L
    q3, L
    q4
    q0, R
    q4, L

    Which of the following strings is accepted by the above FA?

    1. 1100011001000
    2. 1100000000111
    3. 1000001110000
    4. 1100001100110
  17. Choose the incorrect statement
    1. Moore and Melay machines are FSMs with output capability.
    2. Any given Moore machine has an equivalent Melay machine.
    3. Any given Melay machine has an equivalent Moore machine.
    4. Moore machine is not a FSM.
  18. The major difference between Moore and Melay machines is that
    1. The output of the former depends on the present state and present input.
    2. The output of the former depends only on the present state.
    3. The output of the former depends only on the present input.
    4. None of the above.
  19. An FSM with output capability can be used to add two given integers in binary representation. This is
    1. True
    2. False
    3. May be true
    4. None of the above
  20. A finite-state machine has a single input x, single output Z and the following state-table:
    Present state
    Next state, Z
    x = 0
    x = 1
    A
    D, 0
    B, 0
    B
    B, 1
    C, 1
    C
    B, 0
    D, 1
    D
    B, 1
    C, 0

    If the initial state is unknown, then the shortest input sequence to reach the final state C is

    1. 01
    2. 10
    3. 101
    4. 110
  21. The finite-state machine described by the following state diagram with A as starting state, where an arc label is denoted by x/y (x stands for 1-bit input and y stands for 2-bit output).
    1. Outputs the sum of the present previous bits of the input.
    2. Outputs 01 whenever input sequence contains 11.
    3. Outputs 00 whenever input sequence contains 10.
    4. None of the above.
  22. Let (Me)2 mean that given a Melay machine, an input string is processed and then the output string immediately is fed into the machine (as input) and reprocessed. Only this second resultant output is considered the final output of (Me)2. If the final output string is the same as the original input string, we say that (Me)2 has an identity property. Symbolically, we write (Me)2 = identity. Consider the following machines.

    Which of the above machines have the identity property?

    1. i) only
    2. i) and ii) but not iii)
    3. i) and iii) but not ii)
    4. All have identity property.
  23. Let (Me1) (Me2) mean that an input string is processed on Me1 and then the output string is immediately fed into Me2 (as input) and reprocessed. Only this second resultant output is considered the final output of (Me1)(Me2). If the output string is the same as the original input string, we say that (Me1)(Me2) has the identity property, symbolically written (Me1)(Me2) = identity. Consider following machines.

    Which of the following is most appropriate?

    1. (Me1)(Me2) = (Me2)(Me1)
    2. (Me2) is the inverse machine of Me1
    3. (Me1) is the inverse machine of Me2.
    4. All of the above are false.
  24. Consider the following FAs:

    Which of the following is true?

    1. FA1 ⊂ FA2
    2. FA2 ⊂ FA1
    3. FA1 = FA2
    4. none of the above
  25. Consider a DFA over ∑ = (a, b) accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?
    1. 8
    2. 14
    3. 15
    4. 48
  26. What is the number of states in the minimized DFA that accepts all strings whose 7th symbol from Right end is 1
    1. 254
    2. 256
    3. 8
    4. 237
  27. Which of the following statements is true?
    1. The union of two equivalence relations is also an equivalence relation.
    2. Regularity is preserved under the operation of string reversal.
    3. All subsets of regular sets are regular.
    4. A minimal DFA that is equivalent to a NFA with n nodes has always 2n states.
  28. Identify correct statements from the following.

    I. A FSM can be designed to add two integers of any arbitrary length (arbitrary number of digits).

    II Every subset of a countable set is countable.

    1. I only
    2. Neither I nor II
    3. II only
    4. I and II
  29. How many states are there in minimized DFA of the following DFA:
    1. 2
    2. 4
    3. 3
    4. 5
  30. Consider the sequential machine M given below:
    0
    1
    A
    C, 0
    B, 1
    B
    F, 1
    D, 1
    C
    D, 0
    E, 1
    D
    C, 0
    F, 1
    E
    D, 1
    C, 1
    F
    C, 1
    C, 1
    G
    C, 1
    D, 1

    Which of the following sequential machines is the standard (i.e. reduced equivalent machine of M)?

    1. 0
      1
      A
      B, 0
      C, 1
      B
      B, 0
      D, 1
      C
      D, 1
      B, 1
      D
      B, 1
      B, 1
    2. 0
      1
      A
      B, 0
      C, 1
      B
      D, 1
      B, 1
      D
      A, 1
      A, 1
      E
      D, 1
      A, 0
    3. 0
      1
      A
      B, 0
      C, 1
      B
      B, 0
      C, 1
      C
      C, 1
      B, 1
    4. 0
      1
      A
      B, 0
      C, 1
      B
      B, 0
      C, 1
      C
      C, 1
      B, 1
  31. One fine day I draw a DFA for a language which I know very well and place in the house. On that night my house was robbed. The robber did the following:

    He just removed one of non-starting states from my DFA, removed all edges associated with it, redrew it on another paper and robbed my original paper. Next day morning I found that my paper was robbed and saw another FA there. From that day I am thinking what language could be accepted by that FA. My original DFA is shown below.

    Can you help me in finding out the state to be removed to satisfy the following.

    1. The finite automata accepts all strings whose last but one symbol is 1.
    2. The finite automata accepts all strings which end with 11.
    1. A
    2. B
    3. C
    4. D

Answers

  1. c
  2. a
  3. c
  4. c
  5. b
  6. d
  7. c
  8. c
  9. c
  10. a
  11. b
  12. a
  13. c
  14. c
  15. b
  16. d
  17. d
  18. b
  19. a
  20. a
  21. a
  22. d
  23. d
  24. c
  25. d
  26. b
  27. b
  28. d
  29. c
  30. a
  31. c

Exercises

  1. Define a DFA with an example?
  2. Design a DFA which accepts any number of a’s followed by a string ba followed by a string a’s and b’s?
  3. What is a transition graph and transition table?
  4. Obtain a DFA to accept strings of a’s and b’s, except those containing a substring aab?
  5. Design a DFA to accept strings having
    1. exactly one a
    2. at least one ‘a’
    3. not more than 3a’s
  6. Obtain a DFA to accept strings of 0’s, 1’s and 2’s, beginning with a 1, followed by odd number of 0’s and ending with a 2?
  7. Obtain a DFA to accept strings starting with two 0’s and ending with at least two 1’s?
  8. Obtain a DFA to accept a strings of a’s and b’s with at most two consecutive b’s [abababb]?
  9. What is a NFA, write the procedure to convert a NFA to a DFA?
  10. Obtain a DFA to accept the integer numbers represented in binary and is a multiple of 5.
  11. Obtain a DFA to accept a language L that has strings of a’s and b’s ending with ab.
  12. Construct a DFA to test whether a binary number is
    1. Divisible by 6
    2. Divisible by 7
  13. Obtain a DFA whose number of a’s is divisible by 7 and number of b’s is divisible by 5?
  14. Obtain a DFA to strings that begin or end with 0, 1?
  15. Construct a DFA to accept the strings over z = {a, b} with the property that every block of length of 5 contains at least two a’s?
  16. Write the differences between DFA and NFA?
  17. Obtain a DFA to accept a language L that has strings of a’s and b’s ending with ab or ba.
  18. Convert the following NFA into its equivalent DFA.
  19. Define epsilon-closure?
  20. Obtain a DFA to accept a language L that has strings with a’s and b’s such that difference in number of a’s and b’s is multiple of 3.
  21. Obtain a DFA to accept the language L = {awa |w is string with a’s and b’s}
  22. Convert the given ɛ -NFA to its equivalent DFA.
  23. Define the following terms:
    1. DFA
    2. NFA
    3. ɛ-NFA
  24. Construct DFAs that accept the following languages on the alphabet ∑ = {a, b}
    1. all strings with exactly one a
    2. all strings with at least one a
    3. all strings except those which end with abb
  25. Convert to DFA the following NFA:
     
    0
    1
    q0
    q1
    φ
    *q1
    q0
    q1, q2
    q2
    φ
    q1
  26. Define finite automata. Discuss why we study Automata.
  27. Design the DFAs for the following languages.
    1. L = {w/|w| mod 3 = 0, w is string with a’s and b’s}
    2. set of all strings (on the alphabet ∑ = {0, 1}) that either begin or end, or begin as well as end with the substring 01
    3. decimal strings divisible by 3
  28. Explain the procedure to construct DFA for the given NFA using subset construction scheme.
  29. Show that every positive integer can be expressed as a product of prime numbers.
  30. Design a NFA to recognize the following set of the strings:
    1. abc, abd, aacd
    2. 0101, 101, 011 ∑ = {0, 1}
  31. Obtain a DFA to accept binary numbers (over the alphabets {0, 1}) that are divisible by 5 and start with 1.

    Hint: 101, 1011, 101011 strings should be valid, 0101, 01011 are not valid.

  32. Obtain a DFA to accept a language L = {w/|w|mod 3 > = |w|mod 2} where w Σ * and ∑ = {a, b}

    Hint: Strings of length 3, 9, 15, 21 are not valid or in general 3 + 6 n/n ≥ 0 are not valid.

  33. Consider the DFA
    0
    1
    →A
    B
    A
    B
    A
    C
    C
    D
    B
    *D
    D
    A
    E
    D
    F
    F
    G
    E
    G
    F
    G
    H
    G
    D
    1. Draw the table of distinguishabilities for the DFA
    2. Construct the minimum state-equivalent DFA.
  34. Find the language accepted by the following and prove that the FA generates strings where each prefix has at most one more a than b’s and atmost one b more than a’s.

    Hint: This can be proved by deducing the properties of the strings, taking the automaton to each of four states and using mathematical induction on the length of the string.

  35. In converting NFA to DFA, the number of states may increase substantially. Give upper and lower bounds on the maximum increase in number of states for an n-state NFA.

    Hint: Consider the Theorem 1 in 2.4 and the Example 2.17.