Chapter 08. Manipulating Finite State Automata

Models of Language Recognition: Automata

1

8. Manipulating FA In the preceding chapter, when we proved the characterizations among the class of regular languages, FA and regular expressions, we used NFA. If we convert a regular grammar or a regular expression to an FA, the automaton usually turns out to be an NFA. NFA is a conceptual model that cannot be implemented with any currently available technology. However, since every NFA can be converted to a DFA, NFA’s are used as convenient tools for solving problems concerning regular languages or designing DFA’s, which are directly realizable. Figures (a) and (b) below show, respectively, an NFA and a DFA which recognize the same language { xa | x ∈ {a, b}+ }. In this chapter, we will learn how to convert an NFA to a DFA accepting the same language.

a a, b a

b a b

(a) NFA

(b) DFA

When we designed automata, we did not pay much attention on the size of the automata. However, when designing an automaton as a model for implementation, we must take account of the size because it may directly affect the size or the complexity of the implemented hardware or software.

2

Manipulating FA Figures (a) and (b), respectively, show pairs of DFA and DPDA (of different size), respectively, accepting the languages a* and {aibi | i > 0}. Given an arbitrary deterministic automaton (not to mention a nondeterministic one), it is very difficult problem to reduce the number of states of the automaton. No practical algorithms are available except for DFA. For TM and LBA the problem is unsolvable, and it remains as an open problem for PDA’s. We will shortly learn how to minimize a DFA.

(b, a/ε )

a a

a

L = {aibi | i > 0} (a, a/aa)

start

(ε , Z0/Z0) (b, a/ε ) a

L = a*

(a, Z0/aZ0), (a, a/aa)

(a, Z0/aZ0) start (a) Equivalent DFA

(b, a/ε )

start

(ε , Z0/Z0) (b, a/ε )

start

(b) Equivalent DPDA

3

Manipulating FA

8.1 Converting an NFA to DFA 221 8.2 State Minimization 224 Rumination 231 Exercises 236

Family Gift

Break Time

Amanpreet heard a rumor that his father, grandfather and great-grandfather had all walked on water on their 21st birthdays. So, on his 21st birthday, Amanpreet and his good friend Brian headed out to the lake. "If they did it, I can too!" he insisted. When Amanpreet and Brian arrived at the lake, they rented a boat and began paddling. When the got to the middle of the lake, Amanpreet stepped off of the side of the boat . . . and nearly drowned. Furious and somewhat shamed, he and Brian headed for home. When Amanpreet arrived back at the family farm, he asked his grandmother for an explanation. "Grandma, why can I not walk on water like my father, and his father, and his father before him?“ The feeble old grandmother took Amanpreet by the hands, looked into his eyes, and explained, "That's because your father, grandfather, and great-grandfather were born in January . . . you were born in July, dear.“ - Raman -

4

Manipulating FA

8.1 Converting NFA to DFA In this section we will study how to convert an NFA M = (Q, ∑, δ , q0, F) to a DFA M’ = (Q’, ∑, δ ’, q0, F’) which recognizes the same language. Let t ∈∑ and A, B ⊆ Q. Extend δ such that δ (A, t) gives the set of next states that M enters, after reading the symbol t in every state in A. To convert M to M’, first let q0 be the start state of M’ and compute the set δ (q0, t) = A, for every t ∈∑. Then in M’ create a new state labeled with A and add the transition δ ’(q0, t) = A (see figure (b)). For each new state A created, compute δ (A, t) = B, for each t ∈∑, create a state labeled B, if A ≠ B, and add the transition δ ’(A, a) = B, and so on. This procedure is repeated until no new state is added to M’. This idea is best understood by the following example. A a b b c a N a b,c b I a {0,1} {1,2} 1 2 0 0 c c start start b,c b, c {2} c (a) NFA M (b) DFA M’ 5

Manipulating FA

Converting NFA to DFA

Now, finally, we define accepting states in M’. Suppose that A ⊆ Q is defined as a state of M’. This implies that for a string x, if δ ’(q0, x) = A, then reading string x, the NFA M simultaneously enters into all states in A. If there is an accepting state i in A, then by definition, x is accepted by M ignoring all nonaccepting cases. Thus, to make M’ accept the same language, we must define A as an accepting state, as figure (b) below illustrates. If A contains no accepting state, then state A in M’ remains as a non-accepting state. i

start

j

... k

x

(a) Nondeterministic transition in M

x

{. . i, j, . .k.}

start (b) Deterministic transition in M’

6

Manipulating FA

Converting NFA to DFA

In the example, since state 2 is the only accepting state of M, in M’ we define every state labeled with a state set containing 2 as an accepting state. It is easy to prove that L(M) = L(M’). (For the proof, it is enough to show that for every string x ∈ ∑ *, x is accepted by M if and only if x is accepted by M’. We leave the proof for the reader.) Convert to deterministic a b c b a transitions a b,c 1 2 0 a {0,1} b

start

start

(a) NFA

a a 0

start (c) DFA

c

0

b,c b b

{0,1} c

b, c

{1,2} c

{1,2}

b,c

c

{2}

Define accepting states (b)

c A N I

{2} c 7

Manipulating FA

8.2 State Minimization This section presents a method for minimizing the number of states of a DFA. For the method we need the following definition. Let M = (Q, ∑, δ , q0, F) be a DFA. Two states p, q ∈Q are equivalent if they satisfy the following condition. For every w ∈∑ *, δ (p, w) enters an accepting state if and only if δ (q, w) does. The state minimization technique searches all equivalent states and merges them into one state. To see how the technique works, consider the following DFA in figure (a). Notice that for every input string w ∈ {a, b}*, δ (3, w) enters an accepting state if and only if δ (4, w) does. Hence, we can merge states 3 and 4 without affecting the language recognized a by the DFA, as shown in figure a (b). b b a a a 3 a a 2 1 4 2 1 [3,4] b b b (a) (b) 8

Manipulating FA

State Minimization

Clearly, states 2 and [3, 4] in figure (b) are equivalent and hence, we can merge them as shown in figure (c) below. Notice that we cannot merge the two states in figure (c), because one is an accepting state and the other is not. They are not equivalent, because, for w = ε , δ ([2, 3, 4], w) = [2, 3, 4], which is an accepting state, while δ (1, w) = 1 is not. In other words, accepting states and non-accepting states cannot be equivalent. Now, with this conceptual foundation, we are ready to study a systematic approach to minimizing a DFA. a a b b 1

a

2

a

3 b

(a)

a

1

4

b a 1

a

a

(b)

2

a

[3,4]

b

[2,3,4]

b (c) 9

Manipulating FA

State Minimization

There are several algorithms available for finding equivalent states of a DFA to merge and minimize the number of states. We will study an algorithm, called the state partitioning technique, which is easy to follow with an example. Example 1. Consider the DFA M in figure (a) below. We iteratively partition the states of M into groups such that no two states belonging to different groups are equivalent. Since accepting states and non-accepting states cannot be equivalent, we first partition the states into two groups P1 and P2 , the one accepting and the other non-accepting, as shown in figure (b). a

b a start

a

1

a b

0 b

2

3

a b

(a) DFA M

4

{ 3, 4, 5 }

b

b 5

P1

P2 { 0, 1, 2 }

a (b) Initial partitioning 10

Manipulating FA

State Minimization

Now, we analyze the responses of each state for every input symbol in the alphabet {a, b} as follows. For each state q and a symbol t ∈ {a, b}, if δ (q, t) = r and state r belongs to group Pi , we record that the response of state q for the input t is Pi , as shown in figure (a). Clearly, no two states showing different responses can be equivalent, because reading either a or b, one goes to an accepting state and the other goes to a nonaccepting state. So, we partition the groups P1 and P2 as shown in figure (b).

P1 p1 a→ ↑ {3, b→ ↓ p2

p1

P2 p1

p2

p1

↑ ↑ ↑ ↑ 4, 5 } {0, 1, ↓ ↓ ↓ ↓ p p1 p2 p1 (a) 1Response analysis

p1

P11

P12

↑ 2} ↓ p1

{3}

{4, 5}

P21 {0}

P22 {1, 2}

(b) Partitioning 11

Manipulating FA

State Minimization

Having P1 and P2 partitioned into the four new groups, again we need to make sure that all the states in each group are equivalent by analyzing their responses to each input. Suppose that states i and j in a group show different responses. Then, there must be an input string (of length 2 or longer) for which i enters in an accepting state, while j does not, or vice versa. They cannot be equivalent, and should be partitioned into different groups. For the example, the response analysis below shows that all the states in every group show the same responses. We stop the partitioning. Let p and q be two states belonging to a group of the final partition. For an arbitrary input string w ∈{a, b}*, both δ (p, w) and δ (q, w) will enter a state which belongs to the same group. Since all the states in a group are either accepting or nonaccepting, δ (p, w) enters an accepting states if and only if δ (q, w) does. They are equivalent and hence, we can merge them into one state to reduce the number of states. P11 P12 P21 P22

p12 p12 {3}

a→

↑

↑

{4, 5}

b→ ↓ ↓ p12 p12

p11 p11 {0}

↑

↑

↓

↓

{1, 2} p12 p12 12

Manipulating FA

State Minimization

Thus, for the example, merging the two states in {1, 2} and {4, 5}, we get the minimized DFA shown in figure (b) below.

a

b a start

a

1

b

{4, 5}

{0}

2

(a) DFA

a b

{1, 2}

3 a

b

0

{3}

4 b

b 5

0 a

a

b

start

a, b

1,2

3 a

b

a, b 4,5

(b) Reduced DFA

13

Manipulating FA

State Minimization

Example 2. The figure below shows the results of state partitioning. It shows no two states are equivalent, i.e., the DFA is already minimized. For this simple DFA, we can get the same conclusion by the following observation: δ (2, aaa) = 5 is accepting, while δ (3, aaa) = 1 is not. So, states 2 and 3 are not equivalent. Likewise, δ (3, aa) = 5 is accepting, while δ (4, aa) = 1 is not, and hence states 3 and 4 are not equivalent, and so on. a 1

a

2

a

3

a

4

a

P1

5

P21 p21 p21 p22

a→ P1

P22

↑ ↑ ↑ {2, 3, 4} { 5 }

{1}

P2 p2 p2 p2 p1

a→ {1}

{1} {5}

{2}

↑ ↑ ↑ ↑ {2, 3, 4, 5 }

{3}

{4}

P1

P211 p211

a→ {1}

↑ {2,

P212

P22

p212 ↑ 3}

{4}

{5} 14

A N I

Manipulating FA

Rumination (1): State Minimization •

Here we present another algorithm for minimizing a DFA. This approach iteratively identifies state pairs which are not equivalent. For the same previous example (repeated in figure (a) below), the matrix in figure (b) shows the initial contents (the x marks) for all accepting and non-accepting state pairs, which are not equivalent. The matrix has an x mark at entry [i, j], if states i and j are not equivalent. Blank entries are to be resolved.

a

b a start

a

1

b

2

3 a

b

0 2

(a) DFA

a b

4 b

b 5

1

a

i 3 x x x 4 x x x 5 x x x 0 1 2 4 j

3

(b) Matrix of state pairs not equivalent

15

Manipulating FA

Rumination (1): State Minimization

To resolve the entry [4, 3], we examine the two states δ (4, b) = 5 and δ (3, b) = 1. Since [5,1] is marked with x, the entry [4, 3] is also marked with x. Notice that since δ (4, a) = 4 and δ (3, a) = 3 and entry [4, 3] is unresolved, we cannot use this information. Likewise, we find the pairs [5, 3], [1, 0], and [2, 0] are not equivalent. Now, we examine [2,1]. Since δ (2, b) = 5, δ (1, b) = 4, and entry [5, 4] is not resolved yet, we defer the resolution till [5, 4] is resolved. Since δ (4, a) = 4 and δ (5, a) = 5, and δ (4, b) = 5 and δ (5, b) = 4, we mark entry [5, 4] with E, implying that states 4 and 5 are equivalent. Since δ (1, a) = δ (2, a) = 3, δ (1, b) = 4, δ (2, b) = 5, and [5, 4] is marked with E, entry [2,1] is also marked with E.

a

b a start

a

1

a b

0 b

3

2

(a) DFA

a b

4 b

b 5

a

1 x 2 x E i 3 x x x 4 x x x x 5 x x x x E 0 4

1

2

A N I

3

j

(b) Matrix of state pairs not equivalent

16

Manipulating FA

Rumination (1): State Minimization •

We have studied two methods for minimizing the number of states of a DFA, but no proof is given. We need to prove that after the minimization, no further state reduction is possible. For the proof, let M be a DFA (figure (a)) that we get by applying one of the state minimization methods. Suppose that there is a DFA M’(figure (b)), which recognizes the same language with smaller number of states than M.

w2

w2

q p

start

w1 (a) M

s start

w1 (b) M’

Since M’ is smaller than M, and they recognize the same language, there must be two input strings w1 and w2 such that DFA M’, reading both w1 and w2, enter a state s, while DFA M enters in two different states, p and q. Because they recognize the same language, state s is an accepting state if and only if both p and q are accepting. Because states p and q are distinct in M, which is constructed through the method merging equivalent states, they must not be equivalent states.

17

Manipulating FA

Rumination (1): State Minimization

Since states p and q in M are not equivalent, there will be a string x such that reading x in state p, M enters an accepting state, while, reading the same string x in state q, the machine enters a non-accepting state (see figure (a) below). Now we examine what happens in M’ for the same input strings w1x and w2x. Since M’ recognizes the same language, reading w1x it should enter an accepting state, while reading w2x it enters a non-accepting state. This implies that in state s reading x, M’ takes two different transitions as shown in figure (b). This implies that M’ is an NFA, which contradicts our assumption that M’ is a DFA.

w2

w2

x

q p

start

w1 (a) M

x

A N I

s start

w1

x

x

(b) M'

18

Manipulating FA

Rumination (1): State Minimization

The state minimization methods that we have studied are applicable only to DFA’s. For example, figure (a) shows an NFA where no two states are equivalent. However, figure (b) shows a smaller FA which recognizes the same language.

a

a

a

a

a a (a) May You Have

(b)

Break Time

May you have enough happiness to make you sweet, enough trials to make you strong, enough sorrow to keep you human, enough hope to make you happy and Enough money to buy gift! - Anonymous -

19

Manipulating FA

Exercises

8.1 Using the method presented in this chapter, convert each of the following NFA’s to a DFA. You should also show the procedure that you took for your answer. a, b

a, b a

start

1

2

a

a

3

4

1

start

(a)

ε

2

a

3

a

4

(b)

8.2 Using the state partitioning technique, minimize the following DFA. You should also show how you partitioned the states to get your answer. 0 1 2 1

0

4

0

1

1

0

start

3 1

20

Manipulating FA

Exercises

8.3 Can we reduce the number of states of the following DFA without affecting the language recognized by it? Justify your answer. a 1

2 a

3 a

4 a

5 a

8.4 Let M be an NFA, and M’ be the DFA that we get by the technique presented in Section 8.1 for converting an NFA to a DFA. Prove that L(M) = L(M’). (For the proof, show that for an arbitrary input string w, M accepts w if and only if M’ does.)

21