Pumping Lemma - School of Computer Science

Pumping Lemma for Regular Sets:
Let D = (Q, Σ, δ, q0 , F ) be a DFA.
Let n = |Q|.
Let w ∈ L(D) s.t. |w | ≥ n.
Then
∃x, y , z ∈ Σ?
I
xyz = w
I
|xy | ≤ n
I
|y | > 0, and
I
∀k ≥ 0
s.t. the following all hold:
(xy k z ∈ L(D))
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
proof: Let w ∈ L(D), |w | ≥ n, w = w1 , w2 , . . . , wn · u
w=
w1
q0
w2
q1
w3
q2
u
qn
x
y
z
z }| {
w1 . . . wi
z }| {
wi+1 . . . wj
z
}|
{
wj+1 . . . wn u
q0
qi = δ ? (qi , y )
wn
qn−1
qi
|y | ≥ 1
Thus, xy k z ∈ L(D)
for
qf
∃i < j (qi = qj )
By Pigeon-Hole Principle
w =
···
q3 · · ·
qi
δ ? (qi , z) = qf ∈ F
k = 0, 1, 2, . . .
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
qf
Pumping Lemma for Regular Sets:
Let D = (Q, Σ, δ, q0 , F ) be a DFA.
Let n = |Q|.
Let w ∈ L(D) s.t. |w | ≥ n.
Then
∃x, y , z ∈ Σ?
I
xyz = w
I
|xy | ≤ n
I
|y | > 0, and
I
∀k ≥ 0
s.t. the following all hold:
(xy k z ∈ L(D))
Easiest tool to prove languages not DFA acceptable
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
Prop: E = ar b r r ∈ N is not DFA acceptable.
proof by contradiction:
Assume: E is accepted by DFA D with n states.
you (Dumbledore) choose string:
Let w = an b n
By pumping lemma,
I
I
I
I
w ∈ E = L(D)
Gandalf chooses x, y , z ∈ {a, b}? , s.t.,
w = an b n = xyz
|xy | ≤ n
|y | > 0, and
∀k ∈ N ( xy k z ∈ E )
Since 0 < |xy | ≤ n,
y = ai , 0 < i ≤ n
Thus xy 0 z = an−i b n ∈ E .
an−i b n 6∈ E .
⊥
Therefore E is not DFA acceptable.
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
Prop: M = w ∈ {a, b}? #a (w ) > #b (w ) not DFA-acceptable.
proof by contradiction:
Assume: M is accepted by DFA D with n states.
you choose string:
w ∈ M = L(D)
Let w = an+1 b n
By pumping lemma, Gandalf chooses x, y , z ∈ {a, b}∗ s.t.
I
w = an+1 b n = xyz
I
|xy | ≤ n
I
|y | > 0, and
I
∀k ∈ N ( xy k z ∈ M )
Since 0 < |xy | ≤ n,
y = ai , 0 < i ≤ n
Thus xy 0 z = an+1−i b n ∈ M.
an+1−i b n 6∈ M.
⊥
Therefore M is not DFA acceptable.
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
Prop: P = w ∈ {a, b}? |w | is prime is not DFA acceptable.
proof: Assume: P is accepted by DFA D with n states.
you choose string:
Let w = ap
w ∈ P = L(D)
to get contradiction
where p ≥ n is prime
By pumping lemma, Gandalf chooses x, y , z ∈ {a, b}∗ s.t.
I
w = ap = xyz
I
|xy | ≤ n
I
|y | > 0, and
I
∀k ∈ N ( xy k z ∈ P )
y = ai , 0 < i ≤ n
Thus xy p+1 z = xyzy p = ap ap·i = ap(i+1) ∈ P.
But p(i + 1) is not prime, so xy p+1 z 6∈ P.
⊥
Therefore P is not regular.
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
Pumping Lemma for Regular Sets
Let D = (Q, Σ, δ, q0 , F ) be a DFA.
Let n = |Q|.
You (Dumbledore) choose w ∈ L(D) s.t. |w | ≥ n.
Then Gandalf chooses x, y , z ∈ Σ?
I
xyz = w
I
|xy | ≤ n
I
|y | > 0, and
I
∀k ≥ 0
s.t. the following all hold:
(xy k z ∈ L(D))
Finally, you point out why a contradiction ensues.
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
Next Week’s Goal
Kleene’s Theorem Let A ⊆ Σ? be any language. Then the
following are equivalent:
1. A = L(D), for some DFA D.
2. A = L(N), for some NFA N wo transitions.
3. A = L(N), for some NFA N.
4. A = L(e), for some regular expression e.
5. A is regular.
True by definition: (4) ⇔ (5)
L30: Pumping Lemma
CS250: Discrete Math for Computer Science
Usefulness of Kleene’s Thm
Given a regexp e it is hard to find e s.t. L(e) = Σ? − L(e)
Given DFA D it is easy to find D s.t. L(D) = Σ? − L(D)
D = (Q, Σ, δ, s, F )
D = (Q, Σ, δ, s, Q − F )
Prop: L(D) = Σ? − L(D)
w ∈ Σ? δ ? (s, w ) ∈ Q − F
= w ∈ Σ? δ ? (s, w ) 6∈ F
= Σ? − w ∈ Σ? δ ? (s, w ) ∈ F
proof : L(D) =
= Σ? − L(D)
L30: Pumping Lemma
CS250: Discrete Math for Computer Science

Download Report