Lec3

Lecture 3: Two-way Finite State Automaton
Instructor: Ketan Mulmuley

Scriber: Yuan Li
January 13, 2015
1 Two-way Finite State Automaton

Recall that a two-way deterministic finite state automaton (2-DFA) M =
(Q, Σ, δ, q0 , F ), where q : Q × Σ → Q × {L, R} is the transition function. For
example, δ(q, a) = (p, L) means, at current state p if the symbol is a, then
the next state is p and the head will move left. M accepts a string w if it
stops at a final state, and the head is on the right-most position.
Theorem 1.1. 2-DFA is equivalent to NFA (and thus DFA), that is, if a
language is accepted by some 2-DFA, then there exists an NFA accepting the
same language.
Proof. Given a 2-DFA M = (Q, Σ, δ, q0 , F ), we will construct an NFA M ′ =

(Q′ , Σ, δ ′ , q0′ , F ′ ) such that L(M ) = L(M ′ ).
Before getting into the construction, we need the concept valid crossing
sequence. As the following picture illustrates, the head first moves right in
state q1 , working on the right side of the tape, and then moves left in state
q2 , working on the left side of the tape, and then moves right in state q3 , ...,
finally the head moves left in state qk .
Observe that the followings are true.
• The length k is odd.
• The same state does not repeat at any two odd locations or any two
even locations. (Otherwise, the machine will run into a loop.) This
implies the length k < 2|Q|.
1
Figure 1: valid crossing sequence
Let Q′ be the set of all valid crossing sequences, where |Q′ | ≤ |Q|2|Q| ,
q0 = [q0 ] and F ′ = {[p] : p ∈ F ). For the transition function δ ′ : Q′ × Σ → Q′ ,
δ ′ ([q1 , . . . , qk ], a) = [p1 , . . . , pl ]
if and only if [q1 , . . . , qk ] is a-compatible with [p1 , . . . , pl ], that is, δ(q1 , a) =

(p1 , R), δ(p1 , a) = (q2 , L), . . ., and l = k.
It is an NFA instead of DFA because for any given crossing sequence
[q1 , . . . , qk ], there can be multiple [p1 , . . . , pl ] that is a-compatible with [a1 , . . . , ak ].
Note that in the above construction, |Q′ | = |Q|2|Q| . Converting to DFA,

the number of states would be
′
2|Q | = 2|Q|
2|Q|
.
If |Q| = 10, then the DFA will have 210 states, which is greater than
20
the number of particles in the universe. In that sense, the above theorem
is a purely mathematical statement. Understanding the difference between
polynomial and exponential is what complexity theory all about.
The following exercises are challenging, which says the exponential blow-
up is necessary.
Exercise 1.2 (*). Construct a 2-DFA with |Q| states such that there does not
exist any equivalent NFA with the number of states ≤ |Q|a for any constant
a > 0.
Exercise 1.3 (*). Construct a 2-DFA with |Q| states such that there does
not exist any equivalent DFA with 2|Q| states for any constant a > 0.
a
2
2 Lexical Analyzer
In ALGOL, an identifier has the following form (regular expression)
(letter)(letter + digit)∗
In Fortan,
(letter)(ϵ + letter + digit)∗
Exercise 2.1. Construct a DFA accepting the above regular expressions.
In many compiler, the lexical analyzers are implemented using DFA.
3 Pumping Lemma
Pumping lemma says something about regular language, which is not as great
as its name.
Lemma 3.1 (Pumping Lemma). If L ⊆ Σ∗ is a regular language, then
there exists a constant n such that if z ∈ L and |z| > n, then there exists
u, v, w ∈ Σ∗ such that z = uvw, |uv| ≤ n and |v| ≥ 1 and uv i w ∈ L for any
i ≥ 0.
Proof. Take a DFA M = (Q, Σ, δ, q0 , F ) accepting L, and let n = |Q|. Let
z ∈ L be a string with length |z| > n. Consider the sequence of states in M
accepting z. Since |z| > |Q|, there must exist a state which has been visited
more than once; let p be the first such state. Let u be the string from q0 to
p, and let v be the first loop from p to itself, and let w be the rest.
It is easily checked that all the properties in the lemma are satisfied.
Let us see a few applications of pumping lemma.
Proposition 3.2. L = {0l 1l : l ≥ 0} is not regular.
Proof. Suppose to the contrary that L is regular. Let n be as in the pumping
lemma. Let l > n.
Let z = 0l 1l ∈ L. By the pumping lemma, 0l 1l = uvw, where |uv| ≤ n,
which implies both u and v are consecutive 0’s. By the lemma, uv 2 w ∈ L,
which is a contradiction, because uv 2 w has more 0’s than 1’s.
Proposition 3.3. L = {0i : i ≥ 0} is not regular.
2
3
Figure 2: path accepting z
Proof. Suppose to the contrary that L is not regular. Let n be as in the

pumping lemma. Consider
z = 00 . . . 0} .
| {z
(n+1)2 times
By the pumping lemma, z = uvw where |uv| ≤ n and |v| ≥ 1, and uv 2 w ∈ L.

However,
|uv 2 w| = (n + 1)2 + |v| ≤ (n + 1)2 + n < (n + 2)2 ,
which is a contradiction!
Exercise 3.4. Prove L = {0p : p is a prime} is not regular.
4 Properties of Regular Language

Proposition 4.1. If L is regular, then L = Σ∗ \ L is also regular.
Proof. Let M = (Q, Σ, δ, q0 , F ⊂ Q) be a DFA such that L = L(M ),

and without loss of generality assume M will not get stuck. Let M ′ =
(Q, Σ, δ, q0 , Q \ F ), that is, flip accept states to reject states, and reject states
to accept states.
Proposition 4.2. If L1 , L2 are regular, then L1 ∪ L2 is also regular.
4
Figure 3: ϵ-NFA accepting L1 ∪ L2
Proof. Let M1 , M2 be the NFAs accepting L1 , L2 respectively. Construct

the following NFA with ϵ-moves, which accepts L1 ∪ L2 .
Proposition 4.3. Let L1 , L2 are regular, then L1 ∩ L2 is regular.
Proof. Since L1 , L2 are regular, we have L1 , L2 are regular. Then
L1 ∪ L2 = L1 ∩ L2
is regular, which implies L1 ∩ L2 is regular.

Lec3

Uploaded by

Copyright:

Available Formats

Lec3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec3

Uploaded by

Copyright:

Available Formats

Lecture 3: Two-way Finite State Automaton

Instructor: Ketan Mulmuley

1 Two-way Finite State Automaton

Proof. Given a 2-DFA M = (Q, Σ, δ, q0 , F ), we will construct an NFA M ′ =

• The length k is odd.

if and only if [q1 , . . . , qk ] is a-compatible with [p1 , . . . , pl ], that is, δ(q1 , a) =

Note that in the above construction, |Q′ | = |Q|2|Q| . Converting to DFA,

Proof. Suppose to the contrary that L is not regular. Let n be as in the

By the pumping lemma, z = uvw where |uv| ≤ n and |v| ≥ 1, and uv 2 w ∈ L.

|uv 2 w| = (n + 1)2 + |v| ≤ (n + 1)2 + n < (n + 2)2 ,

Exercise 3.4. Prove L = {0p : p is a prime} is not regular.

4 Properties of Regular Language

Proof. Let M = (Q, Σ, δ, q0 , F ⊂ Q) be a DFA such that L = L(M ),

Proposition 4.2. If L1 , L2 are regular, then L1 ∪ L2 is also regular.

Proof. Let M1 , M2 be the NFAs accepting L1 , L2 respectively. Construct

Proposition 4.3. Let L1 , L2 are regular, then L1 ∩ L2 is regular.

Proof. Since L1 , L2 are regular, we have L1 , L2 are regular. Then

is regular, which implies L1 ∩ L2 is regular.

You might also like