Chapter 04. Automata

Models of Language Recognition: Automata

1

4. Automata In the preceding two chapters we learned several models for language representation; formal grammars, L-systems, syntax flow graphs and regular expressions. The natural languages are communication media, and so are the formal languages. The person who hears a spoken sentence should be able to understand the meaning (i.e., the semantics) of the sentence. In this chapter we will learn how to design machine models (i.e., automata) that recognize formal languages. We are not going to build a model which understands a formal language, but one that recognizes it. Here we use the word “recognize” in a much narrower sense than the word “understand” as follows. For a given language L, we say a machine M recognizes L, if M, given a string x, can output “yes” or give a positive indication if and only if x ∈ L. What does it take for a machine M to recognize a language L? To answer this question it is better to think about a conceptual model, instead of complex computer systems currently available. From 1930’s computer scientists have investigated many machine models, called automata, for language recognition. We will study four popular models – Turing machines, linearbounded automata, pushdown automata and finite automata, respectively, recognizing the languages of types 0, 1, 2, and 3, that we have introduced in Chapter 2. In Chapters 7, 12, and 14 we will study the so-called Chomsky hierarchy (after Noam Chomsky), which shows the hierarchical relationship among the languages and automata. Automata can be classified into two types of models, deterministic and nondeterministic. In this chapter we will first study the deterministic models, which naturally follow our intuition, and then the nondeterministic models in the following chapter.

2

Automata 4.1 Deterministic Turing machines (DTM) 80 Design example State transition graph, State transition table, State transition function Formal definition 4.2 DLBA (Deterministic Linear Bounded Automata) 98 Definition and Design example 4.3 DPDA (Deterministic Pushdown Automata) 100 Definition Design example 4.4 DFA (Deterministic Finite Automata) 111 Definition Design example Rumination 114 Exercises 120

LOVE

Break Time

Love is when you take away the feeling, the passion, the romance and you find out you still love the person. Love comes to those who still hope even though they’ve been disappointed, to those who still believe, even though they’ve been betrayed, to those who still love even though they’ve been deeply wounded before. - Anonymous -

3

Automata

4.1 Deterministic Turing Machines

The Turing machine (TM), introduced by Alan M. Turing in 1936, is a model that can recognize type 0 (phrase structured) languages. In this section we will study the deterministic version of the Turing machine. As illustrated below, a TM has a finite state control with a two-way read/write tape head and one-dimensional tape of infinite length. The finite state control corresponds to the CPU of a modern computer, where the “state” represents the whole information stored in the main memory and registers. The tape is divided into cells, each capable of holding one symbol. It is assumed that initially, an input string over a given alphabet is written on the tape, and the tape head is reading the leftmost symbol. We assume that all the blank cells are written with the blank symbol B. a

b

a

b

b

read/write tape

two-way read/write head finite state control 4

Automata

DTM

In one move (or step) a deterministic Turing machine (DTM) does the following: (1) Read the content of the cell on which the tape head is located. (2) Depending on the symbol read and the current state of the finite state control, write a symbol on the cell, erasing the original symbol. (3) Changing the state (or possibly without changing it) move the tape head left or right, or let it stay on the same cell.

a p

b

a

..

c

b q

a

..

c

b

a

..

p

A N I

We say the DTM accepts the input string if it enters a designated state (called accepting state) after some finite number of moves. 5

Automata

DTM

It is unwieldy to draw the configuration (i.e., the tape and the finite state control) for every step of a DTM to illustrate how it works. Instead we will mainly use a directed graph, called the state transition graph, or occasionally the transition function δ to represent each step as shown in figures (a) and (b), respectively.

next state ( symbol read, symbol written, head direction ) current state

δ (current state, symbol read) = (next state, symbol written, head direction)

(a) (b)

6

Automata

DTM

Figures (a) and (b) below, respectively, show a graph and its functional representation of two steps of a DTM. In the figures, R and L, respectively, denote the tape head moving right and left. We shall use N to denote the head staying on the same cell.

a

b

a

..

c

p

b q

a

..

c

b

a

..

p

q (a, c, R) (b, b, L) p (a)

δ (p, a) = (q, c, R) δ (q, b) = (p, b, L) (b) 7

Automata

DTM

Example 1. Construct a DTM which given the word “mother,” converts it to “father,” and vice versa. After completing the conversion, the DTM must halt in an accepting state. Figure (a) below shows the initial and final configurations of a DTM which does the conversion. (Intermediate configurations are omitted.) Figure (b) shows the state transition graph. In the state transition graph of a DTM, state labels are just for reference and hence, can be omitted, if not needed, as shown in figure (b). m

o

t

h

e

r

s (f, m, R)

f

a

t

h

e

r f

(a) (a, o, R)

f

(B, B, N) (r, r, R)

s start

(m, f, R)

(o, a, R)

(t, t, R)

(h, h, R)

(e, e, R)

(b) 8

Automata

DTM

Notice that depending on the first character (either ‘m’ or ‘f’) read, the machine takes a transition to a different state. After converting the first two characters, it does the same work (i.e., rewriting the “ther” part) by taking the four transitions, and finally, reading the blank symbol B, enters the accepting state (the heavy circle labeled with f). Also notice that the machine cannot enter an accepting state after changing the first two characters. It should make sure that the remaining part of the input is correct.

(f, m, R)

f

(a, o, R)

(B, B, N) (r, r, R)

s

(m, f, R)

(o, a, R)

(t, t, R)

(h, h, R)

(e, e, R)

start

9

Automata

DTM

Example 2. Design a DTM which recognizes the language L = {0n1n | n ≥ 1}. Suppose that string 000111 is initially written on the tape as shown below. How can a DTM M recognize that this string belongs to L? We know that if a string x is in L, there should be the same number of 0’s and 1’s in x, and all the 0’s should come first. We will let M use this property. One idea is to let M move back and forth checking if, for each symbol 0 erased (i.e., rewritten) by a symbol, say X, there is 1 that can be erased by Y. We let M enter an accepting state, if it sees that every pair of 0 and 1 is erased. Before we give a formal definition of M, let’s figure out how the machine should move along the tape to implement this idea. 0

0

0

1

1

1

10

Automata

DTM

Let q0 denote the start state of M. We will use the following state names in which the machine does the following; q1: The state in which the machine, after erasing the leftmost 0 with X, moves right in search of the leftmost 1. q2 : The state in which the machine, after erasing the leftmost 1 with Y, moves left in search of X. q3 : The state in which, after reading X, the machine backs up right to read the leftmost 0, if any.

We will introduce additional states, if needed, while designing M’s work further in detail. 0

0

0

1

1

1

q0 11

Automata

DTM

(a)

X 0 q0

1

1

1

q1

X 0

(b)

0

0 Y 1

1

(a) In start state q0, M reads 0 and erasing it by X, moves right in q1 in search of the leftmost 1. (b) After erasing 1 with Y, M moves left in state q2 in search of X.

q2 X 0

(c)

q2 (d)

0 Y 1

1

q3 X X 0 Y 1 q1

1

(c) Reading X in state q2, M backs up in state q3. (d) Reads the next leftmost 0, if any, and erase it with X and moves right in state q1 in search of the next 1 to be erased. M repeats the procedure (b), (c) and (d). 12

A N I

Automata

DTM

(b)

A N I

X X 0 Y Y 1 q2

(c)

X X 0 Y Y 1 q2

(d)

(f) This is the final phase. In state q3 if M reads Y, not 0, it implies that all 0’s are erased by X. M should make sure that no 1’s remain on the tape. For this, M needs additional states q4 and an accepting state q5.

q3

X X X Y Y 1 q1

(e)

X X X Y Y Y

Reading Y in state q3, M enters state q4 and moves right until it reads the blank symbol and then enters an accepting state q5 .

q2 (f)

X X X Y Y Y q2

q3

q4

q5 13

Automata

DTM

The following state transition graph is a formal representation of how the DTM recognizes the language L = {0n1n | n ≥ 1}.

In q1, after erasing the leftmost 0 with X, keep moving right in search of the leftmost 1.

(0,0,L) (Y,Y,L)

(0,0,R) (Y,Y,R)

(1,Y,L)

In q2, after erasing the leftmost 1 with Y, keep moving left in search of X.

q2

q1 (0,X,R)

Reading X, back up right in state q3.

(X,X,R) (0,X,R)

start

q0

A N I

q3 (Y,Y,R)

(Y,Y,R) q4 In q4, check if all 1’s have been erased with Y.

(B,B,N)

q5

14

Automata

DTM

Only the transitions along a path defined on the graph are legal. Reading a symbol undefined (e.g., reading 1 in state q0 ), implies that M rejects the input. Notice that the sequence of moves along the cyclic transitions through q1, q2, and q3 erases any number (≥ 1) of matching pairs of 0 and 1. We can prove by induction that DTM M enters the accepting state q5 if and only if the input string is in the language L = {0n1n | n ≥ 1}. (0,0,R) (Y,Y,R)

(1,Y,L)

q2

q1

(0,0,L) (Y,Y,L)

(X,X,R) (0,X,R) start

(0,X,R)

q0

q3 (Y,Y,R)

(Y,Y,R) q4

(B,B,N)

q5 15

Automata

DTM

The functional representation of the DTM M that we have designed is given below. In this book we will mainly use the state transition graph to show a DTM and other automata, because it is easier to understand how they work.

State Transition Function δ of M δ (q0, 0) = (q1, X, R)

δ (q1, 0) = (q1, 0, R)

δ (q1, 1) = (q2, Y, L)

δ (q2, 0) = (q2, 0, L)

δ (q2, X) = (q3, X, R)

δ (q3, 0) = (q1, X, R)

δ (q1, Y) = (q1, Y, R)

δ (q2, Y) = (q2, Y, L)

δ (q3, Y) = (q4, Y, R)

δ (q4, Y) = (q4, Y, R)

δ (q4, B) = (q5, B, N)

16

Automata

DTM

A DTM can also be represented with a table, called the state transition table. The table below defines the DTM that we have designed. The states are listed on the first column and the tape symbols on the first row. Table entries contain the triple (next state, symbol written, direction). Blank entries are for the cases of rejecting the input.

State transition table of M 0

1

X

Y

q0

(q1, X, R)

q1

(q1, 0, R)

q2

(q2, 0, L)

(q3, X, R) (q , Y, L) 2

q3

(q1, X, R)

(q4, Y, R)

q4

(q2, Y, L)

B

(q1, Y, R)

(q4, Y, R) (q5, B, N)

q5 17

DTM

Automata

Formally a DTM M is defined with a sextuple M = ( Q, Σ , Γ , δ , q0, F ), where Q: The finite set of states. q0 : The start state (q0 ∈ Q). Σ : The finite input alphabet. Γ : The finite tape alphabet, i.e., the set of symbols that are allowed to be written on the tape, including the blank symbol B. Notice that Σ ⊆ Γ . F: The set of accepting states (F ⊆ Q). δ : The state transition function (δ : Q × Γ → Q × Γ × {L, N, R}), where R, L and N, respectively, denote the direction in which the head moves right, left or stay. Given an input string x, if M enters an accepting state in a finite number of moves, we say M accepts x. The language recognized by M, denoted by L(M), is the set of all strings x in Σ * that are accepted by M, i.e., L(M) = { x | x ∈ Σ *, M accepts x}.

18

Automata

DTM

Example: The DTM M which recognizes L = {0n1n | n ≥ 1} can be formally defined as follows. M = ( Q, Σ , Γ , δ , q0 , F ), where Q = {q0, q1, q2, q3, q4, q5}, Σ = {0, 1}, Γ = {0, 1, X, Y, B}, F = {q5}, and the transition function δ is given by the following state transition graph. (0,0,R) (Y,Y,R)

(0,0,L) (Y,Y,L)

(1,Y,L)

q2

q1 (0,X,R)

(X,X,R) (0,X,R)

start

q0

q3 (Y,Y,R)

(Y,Y,R) q4

(B,B,N)

q5 19

Automata

DTM

The state transition of M shows only the transitions that lead to an accepting state. For example, the graph (repeated below) defines only one transition from the start state q0 for the case when the input symbol is 0. What will happen when the DTM reads 1 in state q0? We assume that in such undefined cases, the machine enters a “dead state” and rejects the input. For simplicity, we do not show such rejecting transitions. (0,0,R) (Y,Y,R)

(0,0,L) (Y,Y,L)

(1,Y,L)

q2

q1 (0,X,R)

(X,X,R) (0,X,R)

start

q0

q3 (Y,Y,R)

(Y,Y,R) q4

(B,B,N)

q5 20

Automata

DTM Unless stated otherwise, the reader may assume the following. • Only lower case letters are used for the input alphabet Σ .

• Initially, the input tape is written with a string x over the input alphabet, i.e., x ∈ Σ *, and the tape head is reading the leftmost symbol, if the input is not εNotice . that these assumptions do not affect the computational capability of the machines. We could assume that the machine’s read/write head is initially positioned at an arbitrary location on the input string. Then we can simply modify the machine, as the following figure illustrates, so that it moves onto the leftmost symbol of the input string and then starts the computation. (X, X, L) (B, B, R)

q0

. . . .

start X: any input symbol 21

Automata

4.2 Deterministic linear bounded automata (DLBA) A DLBA is a DTM whose read/write tape range is bounded by the length of the input string. To indicate this range, the input string is delimited by a pair of boundary markers (the matching brackets) as shown below. During the computation, if the DLBA read one of the markers, it should either halt or move back toward the direction it came from. Note that the boundary markers ‘[‘ and ‘]’ are in Γ . Formally a DLBA is defined with an octuple including the boundary markers as shown below. Except for the boundary markers, other elements of the octuple and the language recognized by the automaton are specified as in the formal definition of a DTM.

M = (Q, Σ , Γ , δ , q0, [, ],

[

a

b

a

a

b

]

F) q0

22

Automata

DLBA

With a simple modification of the DTM recognizing {0n1n | n ≥ 1} as shown below, we can make the state transition graph of a DLBA which recognizes the same language. Notice that in state q4, reading the closing boundary mark ‘]’ (instead of the blank symbol B), the machine enters the accepting state. All the other moves are identical to the ones of the DTM. (0,0,L) (Y,Y,L)

(0,0,R) (Y,Y,R)

(1,Y,L)

q2

q1 (0,X,R)

(X,X,R) (0,X,R)

start

q0

q3 (Y,Y,R)

(Y,Y,R) q4

( ], ], N )

q5 23

Automata

4.3 Deterministic pushdown automata (DPDA) A deterministic pushdown automaton (DPDA) is a restrictive version of the DTM. The capacity of the two-way read/write tape head is restricted to one-way read-only and instead, the machine is equipped with a pushdown stack as shown below. In each move the machine does the following: (1) Read the stack-top symbol. (2) Depending on the stack-top symbol and the current state, either read the input or do not read it. (3) Depending on the input symbol read (if it was allowed to read) and the stack-top, pop the stack-top symbol or push some symbols, possibly changing the stack-top. a

b

b

a

a

b

one-way read only

finite state control

push down stack Z0 24

Automata

DPDA

Notice that depending on the state and the stack top symbol, the input head is either allowed to read or not. Reading the input tape, the head should move right onto the next cell. Otherwise, it does not move. The stack head is always positioned at the stack top. We assume that at the bottom of the stack, a designated bottom of the stack symbol (Z0) is initially written.

a

b

b

a

a

b

one-way read only

finite state control

push down stack Z0

25

Automata

DPDA

As we did for DTM and DLBA, we shall mainly describe a DPDA with the state transition graph or the transition function δ as shown below. To denote a move of not reading the input tape, we shall use the null character ε for the parameter “input symbol read.” We call it an ε -move. If the parameter “stack-top content changed” is ε , it is a popping move, i.e., the stack-top symbol is erased.

next state ( input symbol read, stack-top symbol /stack-top content changed) current state

(a)

δ (current state, input symbol read, stack-top symbol) = (next state, stack-top content changed)

(b) 26

Automata

DPDA

The following figures show a sequence of moves of a DPDA and their representations in terms of the transition function δ and the state transition graph. Notice that the second move is an ε -move.

a b c

a b c

a b c

a b c

p

q

r

q

…

Z

…

X Y

…

X V

…

X

δ ( p , a, Z ) = ( q,YX ) p

δ ( q, ε , Y ) = ( r, δ ( r, b, V ) = ( q, ε V) ) A (a, Z /YX) (ε , Y/V) N q r I (b, V/ε ) 27

DPDA

Automata

Formally a DPDA M is defined by the following septuple M = ( Q, Σ , Γ , δ , q0 , Z0, F ), where Q is the set of states, Σ is the input alphabet, Γ is the stack alphabet, δ is the transition function, q0 is the start state, Z0 is the bottom of the stack symbol, and F is the set of accepting states. The function δ , given the current state, the stack-top symbol and the input symbol read or ε (for ε -move), outputs the next state and a string of stack symbols with which the stack-top symbol is replaced, i.e., δ

: Q × ( Σ ∪ {ε } ) × Γ → Q × Γ

*

According to the above definition, M can rewrite the stack-top symbol with a string (of stack symbols) of finite length (including the null string). For convenience we can simplify the stack operation such that the machine either pops the stack-top or pushes one symbol on top of the stack without affecting the language recognized by the machine. At the end of this chapter we will show how.

28

DPDA

Automata

Starting with the initial configuration with the input head on the leftmost symbol and the stack head at the bottom of the stack, a DPDA M accepts the input if and only if it enters a configuration satisfying the following two conditions. (Notice that the conditions are irrelevant to the stack contents.) (1) The input head has read the input string up to the last symbol. (2) The machine is in an accepting state (qf in figure (b)). a

b

b

a

a

a

b

b

q0

a

a

qf

Z0

Z0

(a)

X (b)

The language L(M) is the set of input strings accepted by M, i.e., L(M) = { x | x ∈ Σ

*

, M accepts x } 29

Automata

Designing a DPDA Example 1. Design a DPDA M which recognizes L = {aibi | i > 0}.

Here is a simple idea. Reading a’s, M pushes them in the stack, and then, for each b read from the input tape, the machine erases one a by popping it from the stack top till it sees Z0 (i.e., the stack is empty). Seeing the stack is empty, M enters an accepting state without reading the input. The state transition graph of M is shown below. The best way to understand how this DPDA works is to trace its moves along the transition graph. See how M accepts the input string aaabbb and fails to accept aaabb.

a

a

a

b

b

b

(a, a/aa)

(b, a/ε )

q0 Z0

start

(a, Z0/aZ0)

(ε , Z0/Z0)

(b, a/ε )

30

Designing a DPDA

Automata

Example 2. Design a DPDA which recognizes {aibj | j > i > 0 }. We will use the same idea of pushing a’s and then, for each b read, popping one a from the stack top. Notice that by the time the stack is empty (i.e., Z0 appears at the stack top), the machine has read the same number of a’s and b’s. It should make sure that there are more b’s in the tape by reading them up to the last one. To do this the machine reads one more symbol and if it is a, enters an accepting state. In the accepting state the machine reads off all the remaining b’s, if any.

(a, a/aa)

(b, Z0/Z0)

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

start

(a, Z0/aZ0)

(b, a/ε )

31

Designing a DPDA

Automata

Example 3. Design a DPDA that recognizes language {aibj | i > j > 0 }. Notice that this language has more a’s than b’s. The figure shown below is a DPDA that recognizes this language. Notice that this machine reads the first a and discards it. Then the machine pushes all the remaining a’s onto the stack and reading the first b, enters an accepting state. And in the accepting state, read off all the remaining b’s, popping one a from the stack top for each b read. Because all the a’s in the input except the first one have been pushed into the stack, during the popping phase it is guaranteed that the total number of a’s read from the input tape is strictly greater than the number of b’s. See how this DPDA works by tracing its moves for the input strings aaabb and aabbb. (a, Z0/aZ0) (a, a/aa)

start

(a, Z0/Z0)

(b, a/ε )

(b, a/ε )

32

Automata

Designing a DPDA

For comparison, here are the three state transition graphs that we have designed in the previous examples. {aibi | i > 0 } (a, a/aa)

start

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

(b, a/ε )

(a, Z0/aZ0)

(b, a/ε )

(ε , Z0/Z0)

(b, a/ε )

(a, a/aa)

{aibj | i > j > 0 }

start

(a, Z0/Z0)

(b, a/ε )

(b, Z0/Z0)

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

start

(a, Z0/aZ0)

(b, a/ε )

{aibj | j > i > 0 } 33

DPDA 설계

Automata

Example 4. Design a DPDA which recognizes the following language. {aibkci | k, i > 0 } ∪ {aibkdk | k, i > 0 } Notice that to recognize the first half of the language, the machine needs to push a’s into the stack to match with c’s. However, we cannot let the machine read off b’s and discard them, because the input string may belong to the second half of the language. The machine needs all a’s and b’s (in this order) pushed into the stack till it reads c or d from the input tape. Reading c, we let it pop out all the b’s in the stack before it begins matching a’s and c’s. (ε , b/ε ) (ε , a/ε ) (c, a/ε ) (a, a/aa)

start

(a, Z0/aZ0)

(c, b/ε ) (b, a/ba)

(ε , Z0/ Z0)

(d, b/ε )

(b, b/bb)

(ε , a/a) (d, b/ε ) 34

Automata

4.4 Deterministic finite automata (DFA)

Deterministic finite automata (DFA) are the simplest computational model, which can recognize only regular languages. A DFA is a DPDA with the pushdown stack removed. Thus a DFA M is defined with the quintuple M = ( Q, Σ , δ ,q0 , F ), where Q, Σ , q0, and F are the same as they are defined for a DPDA. The transition function δ is the mapping δ : Q × Σ → Q. In a move the machine reads the input tape, and depending on the current state and the input symbol read, it enters a state in Q and moves right. For example, δ (p, a) = q implies a move shown in figure (a) below, which can be represented with the state transition graph shown in figure (b).

a a b p

One-way read only

q (a)

q

a

a a b p

(b) 35

DFA

Automata

A DFA accepts the input string if and only if it satisfies the following two conditions, which are the same for DPDA’s. (1) The input head has read the input string up to the last symbol. (2) The machine is in an accepting state. The language recognized by a DFA M, denoted by L(M), is L(M) = { x | x ∈ Σ

*

, M accepts x }

Example 1. Construct a DFA which recognizes the following language. L = {x | x ∈ {0, 1}+, the number of 1’s in x is odd} Here is the transition graph of a DFA which recognizes the language L.

0 start

1

0

1 36

Automata

Designing a DFA Example 2. Design a DFA which recognizes the following language. L = {x | x is a binary number, i.e., x ∈ {0, 1}+, and x mod 3 = 0 }

Let M be a DFA which recognizes L. In addition to the start state, M has 3 states, each labeled with one of the three possible remainders, 0, 1, and 2 (see the graph below). Reading the input binary string, M computes the current remainder on the fly and enters the state labeled with that remainder as follows. 0 0 start

1

0

1 1

1

0 1

0

2

For a binary string w, let dec(w) be the decimal value of w. If the first symbol read is 0, the current remainder is 0, if 1 it is 1. So, depending on the first input symbol read, M enters either state 0 or 1. Suppose that reading up to a prefix v of the input string, M entered a state i ∈ {0, 1, 2}, implying that i = dec(v) mod 3. Reading the next bit j ∈ {0, 1}, M enters a state labeled by dec(vj) mod 3. Since dec(vj) mod 3 = (2dec(v) + j) mod 3 = (2i + j) mod 3, M can easily identify the next state to enter as the transition graph shows. 37

Automata

Rumination (1): States

Every automaton has some states. We have introduced the word “state” without elaborating the deep conceptual issues involved. Actually, by a state we represent the whole information stored in the finite state control that the machine needs for the work. The DTM that we have designed in Example 2 of Section 4.1 has 6 states. In each state qi the machine does a unique work. Erasing the leftmost 0 with X, the machine keeps moving right in state q1 till it reads the leftmost 1. Rewriting this 1 with Y, the machine keeps moving left in state q2 until it reads X (see the top figures (a) through (d) below). Would it be possible to do this part of the work in one state? The answer is no. The figures at the bottom show why. Suppose that the machine, erasing the leftmost 1 by Y, moved left in the same state q1. Then the machine will encounter the same symbol 0 that it came across moving right. Reading this 0 the machine should move right, because the DTM must take the same move (as in figure (a)) with the same input 0 in the same state q1, i.e., δ (q1, 0) = (q1, 0, R). Reading the same 0 second time in state q1, the machine has no information in its finite control that indicates it should move left this time. In its finite control the machine should have some information available that is different from the one when it is in state q1. Being in state q2, different from q1, implies this.

X 0 1 1 .. q1

q1

(a) X 0 1 1 .. q1

X 0 1 1 ..

X 0 Y 1 .. q2

q2

(b)

(c)

X 0 1 1 ..

X 0 Y 1 ..

q1

q1

X 0 Y 1 ..

(d) ?

X 0 Y 1 .. q1 38

Automata

Rumination (1): States

The six states of the DTM in Example 2 (repeated below) can be implemented with a three-bits register, for example, letting its values 000, 001, 010, 011, 100, and 101 represent the states q0, q1, q2, q3, q4, and q5, respectively. The number of states is directly related to the hardware complexity of the machine. Unfortunately, given an arbitrary automaton, it is an unsolvable problem to minimize the number of states of the machine. However, for DFA it is possible to minimize them. We will learn how in Chapter 8.

(0, 0, R) (Y,Y, R)

(0, 0, L) (Y,Y, L)

(1,Y, L)

q2

q1 (0, X, R)

(X, X, R) (0, X, R)

start

q0

q3

X 0

Y

1

..

010

(Y,Y, R)

(Y,Y, R) q4

(B, B, N)

q5

39

Automata

Rumination (2): Accepting conditions

Recall that by the definition, both DTM and DLBA accept the input string by entering an accepting state. Hence, no transition is needed out of an accepting state. We may think that both DTM and DLBA halt in an accepting state. Also recall that both DTM and DLBA can have more than one accepting state (i.e., F ⊆ Q). However, we can show that one accepting state is enough. If it has more than one accepting state, we simply merge them into one as the figure below illustrates. Thus, we can design a user-friendly DTM or DLBA which entering the accepting state, can kindly announce that the input has been accepted. What will happen when the input string is not accepted? Would it be possible to design a DTM which can inform us of not accepting the input? What about the other machine models? We will deal with these intriguing questions and related ones in Chapters 7, 12 and 15, under the title of Hierarchy of Languages and Automata.

In contrast, for both DPDA and DFA the following two conditions should be satisfied simultaneously to accept the input string. (1) The input head has read the string up to the last symbol. (2) The finite state control is in an accepting state. Notice that with no unique marker appended to every input string, it is impossible for both DPDA and DFA to identify whether the symbol read is the last one or not. Figures (a) and (b) below, respectively, show a DPDA and a DFA recognizing the language L = {ai | i > 0 }. Suppose that the string aaaa is given as an input. Reading the first a, the machines enter the accepting state. However, it is too early to say that the input string is accepted because it has not read the last a yet (i.e., the second condition is not yet satisfied). Since the machines keep reading a’s in the accepting state, it will eventually satisfy the two conditions. a (a, Z0/Z0) a (a, Z0/Z0) start

start (a)

(b)

40

Automata

Rumination (2): Accepting conditions

If the input string had a symbol different from a, the machine would fail to accept it because the transitions are defined only for the symbols in the input alphabet. Since the blank symbols does not belong to the input alphabet, the machine cannot read the blank symbol next to the last input symbol to ensure that the symbol read in the previous move is the last input symbol or not. (Such an illegal move is quite tempting for a student designing a DPDA.) From the above analysis we find that both DPDA and DFA are not autonomous computational models that can kindly tell us whether the input is accepted or not. In other words, we cannot make them say “Yes, I accept it!” or “Sorry, I cannot.” Rather we, the user, must decide, for a given input string, whether or not the machine satisfies the two conditions after some finite number of moves. Concerning these accepting conditions, we may raise the following question: Why should we put the burden on the user for the decision? How about appending an end-of-string marker to every input string? Consider the language L’ = {ai ; | i > 0} with a marker ‘;’ appended to every string in L. For such language we don’t need condition (1) above. The input strings will accepted if and only if the machine enters an accepting state (see the figures below). (a, Z0/Z0) start

(a, Z0/Z0)

a a

( ; , Z0/Z0)

start

;

Appending an end-of-string marker to every string appears to alleviate the burden for the user to see if a DPDA or a DFA accepts it. However, this approach introduces a new burden for the user in the real application. For example, programming language C uses such approach (each statement must end by a semicolon) and we know why it is a burden, while FORTRAN does not. In this book we mainly study the automata whose languages have no end-of–string markers. Recall that for both DTM and DLBA, the only accepting condition is to enter an accepting state. The user does not have to check if the last input symbol has been read. They can identify the last symbol by reading the next neighboring symbol, i.e., the blank symbol for DTM and the right boundary marker ‘]’ for DLBA. (Notice that blank symbol belongs to the tape alphabet that the DTM can read.) Since the tape head of these models is bidirectional, they can accept the input string with the head located at any position.

41

Automata Rumination (3): Stack operation of DPDA By definition, in every move, a DPDA rewrites the stack-top symbol with a string of finite length (including the null string). (Notice that rewriting the stack-top with the null string implies a popping operation.) This stack operation can be simplified such that the stack-top symbol is either popped out or exactly 1 symbol is pushed on top of the stack without affecting the language recognized by the machine. (Notice that in this simplified version, there is no stack operation rewriting the stack-top symbol with another.) Suppose that as illustrated in figure (a) below, there is a DPDA which has a stack operation rewriting the stack-top with a string of length either 1 (i.e., simply replaces the stack-top with another) or greater than 2 (i.e., pushes more than 1 symbol on top of the stack). Figure (b) shows a simplified version of figure (a). Notice that the stack operation involved in the transition with (b, A/B) is replaced by two transitions with a pushing operation (b, A/XB) followed by a popping operation (ε , X/ε ), where X is a new stack symbol introduced. It is clear from the transformation that such simplification does not affect the language recognized by the DPDA.

(ε , X/ε ) (b, A/XB)

(b, A/B)

(a, Z0/AaBZ0)

(a, Z0/BZ0)

(ε , a/Aa) (ε , B/aB)

(a)

(b)

42

Automata

Rumination (4): Reading operation of a DPDA

Finally we would like to ruminate on the reading operation of a DPDA and clarify some tricky concepts involved. Recall that a DPDA does the following in a move. (1) In the current state, read the stack-top symbol. (2) Depending on the stack-top symbol and the current state, either read the input or do not read. (3) Depending on the input symbol read (if it was allowed to read in (2) above) and the stack-top symbol, pop the stack-top symbol or push some symbols, possibly changing the stack-top. For a state p, stack symbol A and an input symbol a, if transition δ (p, a, A) is defined, then the above definition implies that transition δ (p, ε , A) should not be defined, and vice versa. To the contrary, suppose that both transitions δ (p, a, A) = (q, BA) and δ ( p, ε , A) = (r, CA) are defined (see the figure below). Transition δ (p, a, A) = (q, BA) implies the following move. (1) In state p, the DPDA reads the stack-top symbol. (This part is always done in any state.) (2) If the stack-top symbol is A, the machine reads the input, and (3) if the input symbol read is a, pushes B on top of the stack and enters state q. In contrast, transition δ (p, ε , A) = (r, CA) implies the follow move: (1) In state p, the DPDA reads the stack-top symbol. (2) If the stack-top is A, the machine does not read the input, and

(ε , A/ CA) p

r

(a, A/ BA)

q

(3) pushes C on top of the stack and enters state r. Notice that in the two moves δ (p, a, A) = (q, BA) and δ ( p, ε , A) = (r, CA), the machine does two contradictory actions (boldfaced phrases) in the same state p with the same stack-top symbol A; in the former move, the machine reads the input symbol, while in the later it does not read the input. This violates the determinism of DPDA that for the same course (i.e., the same state p and stack-top symbol A) there must be a unique response. Deterministic automata do not allow such moves. In the following chapter we will study nondeterministic automata, where such contradictory moves are allowed.

43

Automata Exercises 4.1 Design a DTM which, given a binary number x ∈ {0, 1}+ on the input tape, increments x by one and halts in an accepting state. 4.2 What does the following DTM do? The input is a binary string. Describe the work in detail referring each state. For your answer, it is a good strategy to trace the moves of the machine with a couple of short input strings.

(0,0,L) (1,1,R) (0,0,R)

start

(1,0,L)

0

4

(0,B,L)

(1,1,R) (0,0,R)

(B,0,N)

(B,B,L)

1

2

(B,B,L)

(0,1,L)

3

6

(1,0,L)

(0, 1, R) (B,1,R) (1,B,L)

5

(B,1,N)

(1,1,L)

44

Automata

Exercises

4.3 Design a DTM which, given a string x ∈{a, b}*, does each of the following works and then halts in an accepting state. (a) Shift the string x one cell to the right.

(b) Shift the string x two cells to the right.

4.4 Design a DTM which, given a string x ∈{a, b}*, collects all a’s in x to the left and all b’s to the right. For example, given the string baabbab as an input, your machine should rearrange the symbols in it such that aaabbbb is the only string in the tape. 4.5 Design a DTM which, given a string x ∈ {a, b, c}+, moves all c’s toward the left end of the string and halts. For example, given the string baacbbccabc, the machine should leave only the string ccccbaabbab on the tape and halt. With the transition graph of your machine and an input string, briefly explain how it works. 4.6 Design a DPDA to recognize each of the following languages. (Notice that L1, L2, and L3 have an end-of-string marker ‘;’) (a) L1 = {aibj; | i > j > 0 }

(b) L2 = {aibj; | i ≥ j > 0 }

(c) L3 = {aibj; | i ≥ j ≥ 0 }

(d) L4 = {aibj | i > j > 0 }

(e) L5 = {aibj | i ≥ j > 0 }

(f) L6 = {aibj | i ≥ j ≥ 0 }

(g) L7 = { aibkci | i, k > 0 } (h) L8 = { aibkci | i, k ≥ 0 } 4.7 Design a DPDA to recognize the language generated by each of the following context-free grammars. (a) G1: S → aSbb | abb (b) G2: S → aSbb | ε (c ) G3: S → aSbb | ccc 4.8 Design a DPDA to recognize each of the following languages. L1 = { x | x ∈ {a, b, c}+, in x the number of a’s and the number of b’s are same. } L2 = { x | x ∈ {a, b, c}+, in x the number of a’s is strictly greater than the number of c’s. } 4.9 Design a DFA to recognize each of the following languages. (a) L1 = { babo }

(b) L2 = { xbaboyobba | x, y ∈ {a, b, o}*}

(c) L3 = {x | x ∈ {a, b, c}+ , string x begins and ends with the same letter.}

45

Automata

Exercises

The following problem is for modeling a system by a DFA. The original problem is given as an exercise in the book “Introduction to Automata Theory, Languages, and Computation (page 53) (by Hopcropt, Motwani and Ullman, Edison Wesley, 2001).” Here we present it slightly modified. 4.10 Consider a network of ducts shown below. The network has two entries labeled A and B, and two exits C and D. There are two levers; x1 at the branching section and x2 at the cross-section. If we drop a marble in at A or B, the marble rolls down along the ducks and hits one of the levers, which causes it to fall either to the left or to the right. Whenever a lever is hit by a marble, it causes the lever change its orientation 90o such that the next marble to encounter the lever will be directed to the opposite direction. The initial lever positions are set as shown in the figure, indicating that both levers direct the marble to the right. Model this network by a DFA whose input is a binary string, where 0 denotes a marble dropped in at A, and 1 denotes a marble dropped in at B. The automaton accepts the input if the last marble comes out of exit D.

A

B

x1 x2

C

D

46