close

Вход

Забыли?

вход по аккаунту

?

The Pumping Lemma

код для вставкиСкачать
Pumping Lemma
for
Context-free Languages
Prof. Busch - LSU
1
Take an infinite context-free language
Generates an infinite number
of different strings
Example:
S п‚® ABE | bBd
A п‚® Aa | a
B п‚® bSD | cc
D п‚® Dd | d
E п‚® eE | e
Prof. Busch - LSU
2
In a derivation of a “long” enough
string, variables are repeated
A possible derivation:
S пѓћ ABE пѓћ AaBE пѓћ aaBE
пѓћ aabSDE пѓћ aabbBdDE
пѓћ
пѓћ aaabbccdDE
пѓћ aabbccddE
пѓћ aabbccddeE
пѓћ aabbccddee
Prof. Busch - LSU
3
Derivation Tree
aabbccddee
S
B
A
A
a
a
b
E
S
e
D
E
e
b
B
c
d
d
c
Repeated
variable
Prof. Busch - LSU
4
Derivation Tree
aabbccddee
S
B
A
A
a
a
b
E
S
e
D
E
e
b
B
c
d
d
c
Repeated
variable
Prof. Busch - LSU
5
B пѓћ bSD пѓћ bbBdD пѓћ bbBdd
B
b
S
D
b
B
d
d
*
B пѓћ bbBdd
Prof. Busch - LSU
6
S пѓћ ABE пѓћ AaBE пѓћ aaBE пѓћ aaBeE пѓћ aaBee
S
B
A
A
E
e
a
E
e
a
*
S пѓћ aaBee
Prof. Busch - LSU
7
B
c
c
B пѓћ cc
Prof. Busch - LSU
8
Putting all together
S
B
A
A
a
a
b
S
S пѓћ aaBee
e
D
E
e
b
B
c
*
E
d
d
c
*
B пѓћ bbBdd
Prof. Busch - LSU
B пѓћ cc
9
We can remove the middle part
S
B
A
A
a
c
E
e
c
E
e
a
*
0
0
S пѓћ aa ( bb ) cc ( dd ) ee
Prof. Busch - LSU
10
*
*
S пѓћ aaBee
*
B пѓћ bbBdd
*
S пѓћ aaBee пѓћ aaccee
0
B пѓћ cc
0
0
пЂЅ aa ( bb ) cc ( dd ) ee
0
aa ( bb ) cc ( dd ) ee пѓЋ L ( G )
Prof. Busch - LSU
11
We can repeated middle part two times
S
B
A
A
b
a
1
a
2
S
e
D
E
e
b
B
d
b
S
D
b
B
d
c
*
E
d
d
c
2
2
S пѓћ aa ( bb ) cc ( dd ) ee
Prof. Busch - LSU
12
*
*
S пѓћ aaBee
B пѓћ cc
B пѓћ bbBdd
*
*
S пѓћ aaBee пѓћ aabbBddee
*
2
2
*
2
2
пѓћ aa ( bb ) B ( dd ) ee пѓћ aa ( bb ) cc ( dd ) ee
2
2
aa ( bb ) cc ( dd ) ee пѓЋ L ( G )
Prof. Busch - LSU
13
We can repeat middle part three times
S
B
A
a
A
1
a
2
3
E
b
S
b
B
d
b
S
D
b
B
d
b
S
D
b
B
d
E
e
c
*
e
D
d
d
d
c
3
3
S пѓћ aa ( bb ) cc ( dd ) ee
Prof. Busch - LSU
14
*
S пѓћ aaBee
*
*
B пѓћ bbBdd
3
3
S пѓћ aa ( bb ) cc ( dd ) ee
Prof. Busch - LSU
B пѓћ cc
пѓЋ L (G )
15
Repeat middle part i times
S
B
A
a
A
1
a
b
S
b
B
E
e
D
E
e
d
d
B
i
b
S
D
b
B
d
c
*
d
c
i
i
S пѓћ aa ( bb ) cc ( dd ) ee
Prof. Busch - LSU
16
*
*
S пѓћ aaBee
*
B пѓћ bbBdd
i
i
For any
iп‚і0
S пѓћ aa ( bb ) cc ( dd ) ee
Prof. Busch - LSU
B пѓћ cc
пѓЋ L (G )
17
From Grammar
and given string
S п‚® ABE | bBd
A п‚® Aa | a
aabbccddee
пѓЋ L (G )
B п‚® bSD | cc
D п‚® Dd | d
E п‚® eE | e
We inferred that a family of strings is in L (G )
*
i
i
S пѓћ aa ( bb ) cc ( dd ) ee
пѓЋ L (G )
Prof. Busch - LSU
for any i п‚і 0
18
Arbitrary Grammars
Consider now an arbitrary infinite
context-free language L
Let G
be the grammar of L пЂ­ { пЃ¬ }
Take G so that it has no unit-productions
and no пЃ¬ -productions
(remove them)
Prof. Busch - LSU
19
Let
r
be the number of variables
Let
t
be the maximum right-hand size
of any production
Example:
S п‚® ABE | bBd
A п‚® Aa | a
B п‚® bSD | cc
rпЂЅ5
tпЂЅ3
D п‚® Dd | d
E п‚® eE | e
Prof. Busch - LSU
20
Claim:
r
Take string w пѓЋ L (G ) with | w |пЂѕ t .
Then in the derivation tree of w
there is a path from the root to a leaf
where a variable of G is repeated
Proof:
Proof by contradiction
Prof. Busch - LSU
21
Derivation tree of
S
We will show:
some variable
is repeated
w
| w |п‚і m
H
H
пЃі
Prof. Busch - LSU
22
First we show that the tree of w
has at least r пЂ« 2 levels of nodes
Suppose the opposite:
At most
r пЂ«1
Levels
Prof. Busch - LSU
23
Maximum number of nodes per level
t
Level 0:
1 nodes
Level 1:
t nodes
nodes
The maximum right-hand side of any production
Prof. Busch - LSU
24
Maximum number of nodes per level
t nodes
t
Level 0:
1 nodes
Level 1:
t nodes
Level 2:
2
t nodes
t nodes
2
nodes
Prof. Busch - LSU
25
Maximum number of nodes per level
Level 0: 1 nodes
At most
r пЂ«1
Level
Levels
i
i
: t nodes
Level
r:
t
r
nodes
Maximum possible string length
r
= max nodes at level r = t
Prof. Busch - LSU
26
Therefore,
maximum length of string
w : | w |п‚Ј t
r
However we took, | w |пЂѕ t
r
Contradiction!!!
Therefore,
the tree must have at least r пЂ« 2 levels
Prof. Busch - LSU
27
Thus, there is a path from the root
to a leaf with at least r пЂ« 2 nodes
V1
At least
rпЂ«2
Levels
(root)
V1 пЂЅ S
V2
V3
r пЂ«1
Variables
V r пЂ«1
пЃі
symbol
(leaf)
Prof. Busch - LSU
28
Since there are at most r different variables,
some variable is repeated
S
V1
V2
V3
Pigeonhole
principle
H
H
V r пЂ«1
пЃі
пЃі
Prof. Busch - LSU
END OF CLAIM PROOF
29
w with | w |пЂѕ t
Take now a string
r
S
From claim:
some variable H
is repeated
H
H
пЃі
subtree of
H
Take H to be the deepest, so that
only H is repeated in subtree
Prof. Busch - LSU
30
We can write
w пЂЅ uvxyz
S
yield u
yield v
u , v, x, y, z :
Strings of terminals
Prof. Busch - LSU
H
H
z yield
y yield
x yield
31
Example:
S
B
A
A
u пЂЅ aa
a
v пЂЅ bb
u
b
a
v
S
e
D
E
e
b
B
d
d
y
c
x пЂЅ cc
y пЂЅ dd
E
z
c
x
B correspond s to H
z пЂЅ ee
Prof. Busch - LSU
32
Possible derivations
пЂЄ
S
S пѓћ uHz
z
u
H
пЂЄ
H пѓћ vHy
v
H
y
пЂЄ
Hпѓћx
x
Prof. Busch - LSU
33
u пЂЅ aa
Example:
S
B
A
A
a
a
b
S пѓћ uHz
пЂЄ
S пѓћ aaBee
x пЂЅ cc
E
S
e
D
y пЂЅ dd
E
z пЂЅ ee
e
b
B
c
пЂЄ
v пЂЅ bb
d
d
c
пЂЄ
H пѓћ vHy
пЂЄ
B пѓћ bbBdd
Prof. Busch - LSU
B correspond s to H
пЂЄ
Hпѓћx
B пѓћ cc
34
Remove Middle Part
S
пЂЄ
S пѓћ uHz
u
z
H
пЂЄ
Hпѓћx
x
0
0
Yield: uxz пЂЅ uv xy z
пЂЄ
*
S пѓћ uHz пѓћ uxz
0
0
пЂЅ uv xy z
Prof. Busch - LSU
пѓЋ L (G )
35
Repeat Middle part two times
пЂЄ
S
S пѓћ uHz
z
u
H
пЂЄ
1
H пѓћ vHy
v
H
y
пЂЄ
H пѓћ vHy
v
2
y
H
пЂЄ
Hпѓћx
Yield: uvvxyyz
Prof. Busch - LSU
x
2
2
пЂЅ uv xy z
36
пЂЄ
пЂЄ
S пѓћ uHz
пЂЄ
H пѓћ vHy
*
пЂЄ
Hпѓћx
*
S пѓћ uHz пѓћ uvHyz пѓћ uvvHyyz
*
пѓћ uvvxyyz
2
2
пЂЅ uv xy z пѓЋ L ( G )
Prof. Busch - LSU
37
Repeat Middle part i times
пЂЄ
S
S пѓћ uHz
z
u
H
пЂЄ
y
1
y
i
H пѓћ vHy
v
H
H
пЂЄ
H пѓћ vHy
v
H
пЂЄ
Hпѓћx
x
i
i
Yield: uv xy z
Prof. Busch - LSU
38
пЂЄ
пЂЄ
пЂЄ
S пѓћ uHz
H пѓћ vHy
пЂЄ
пЂЄ
пЂЄ
Hпѓћx
пЂЄ
S пѓћ uHz пѓћ uvHyz пѓћ uvvHyyz пѓћ
пЂЄ
пѓћпЃ‹
пЂЄ
i
i
пЂЄ
i
i
пѓћ uv Hy z пѓћ uv xy z пѓЋ L(G)
Prof. Busch - LSU
39
Therefore,
| w |п‚і t
r
If we know that: w пЂЅ uvxyz
then we also know:
i
пѓЋ L (G )
i
uv xy z пѓЋ L (G )
For all i п‚і 0
since
L ( G ) пЂЅ L пЂ­ {пЃ¬ }
i
i
uv xy z пѓЋ L
Prof. Busch - LSU
40
Observation 1:
S
| vy | п‚і 1
Since G has no
unit and
пЃ¬ -productions
z
u
H
v
H
y
x
At least one of v
or y
Prof. Busch - LSU
is not пЃ¬
41
Observation 2:
| vxy | п‚Ј t
S
r пЂ«1
z
u
since in subtree
only variable H
is repeated
H
v
H
y
x
Explanation follows….
subtree of H
Prof. Busch - LSU
42
subtree of H
vxy пЂЅ s 1 s 2 пЃЊ s k
H
T1
Tk
T2
s1
sk
s2
Various yields
| s j |п‚Ј t
| vxy |пЂЅ
since no variable is repeated in T j
r
k
| sj
| п‚Ј k пѓ—t
r
п‚Ј t пѓ—t
r
пЂЅt
r пЂ«1
j пЂЅ1
Maximum right-hand side of any production
Prof. Busch - LSU
43
Thus, if we choose critical length
m пЂЅt
r пЂ«1
пЂѕt
r
then, we obtain the pumping lemma for
context-free languages
Prof. Busch - LSU
44
The Pumping Lemma:
For any infinite context-free language L
there exists an integer m such that
for any string
w пѓЋ L,
we can write
w пЂЅ uvxyz
with lengths
| vxy |п‚Ј m
| w |п‚і m
and
| vy |п‚і 1
and it must be that:
i
i
uv xy z пѓЋ L ,
for all i п‚і 0
Prof. Busch - LSU
45
Applications
of
The Pumping Lemma
Prof. Busch - LSU
46
Non-context free languages
n n n
{ a b c : n п‚і 0}
Context-free languages
n n
{ a b : n п‚і 0}
Prof. Busch - LSU
47
Theorem: The language
n n n
L пЂЅ { a b c : n п‚і 0}
is not context free
Proof:
Use the Pumping Lemma
for context-free languages
Prof. Busch - LSU
48
n n n
L пЂЅ { a b c : n п‚і 0}
Assume for contradiction that L
is context-free
Since L is context-free and infinite
we can apply the pumping lemma
Prof. Busch - LSU
49
n n n
L пЂЅ { a b c : n п‚і 0}
Let m be the critical length
of the pumping lemma
Pick any string w пѓЋ L with length | w |п‚і m
m m m
We pick: w пЂЅ a b c
Prof. Busch - LSU
50
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
From pumping lemma:
we can write: w пЂЅ uvxyz
with lengths | vxy |п‚Ј m
Prof. Busch - LSU
and | vy |п‚і 1
51
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
Pumping Lemma says:
i
i
uv xy z пѓЋ L
for all
Prof. Busch - LSU
iп‚і0
52
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
We examine all the possible locations
of string vxy in w
Prof. Busch - LSU
53
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Case 1:
m
vxy
| vxy |п‚Ј m
is in a
| vy |п‚і 1
m
m
m
a ... aa ... aa ... a bbb ... bbb ccc ...ccc
u
vxy
z
Prof. Busch - LSU
54
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
v пЂЅa
| vxy |п‚Ј m
k1
y пЂЅa
k1 пЂ« k 2 п‚і 1
k2
m
| vy |п‚і 1
m
m
a ... aa ... aa ... aa ... aa ... a bbb ... bbb ccc ...ccc
u
v
x
y
z
Prof. Busch - LSU
55
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
v пЂЅa
| vxy |п‚Ј m
k1
y пЂЅa
k1 пЂ« k 2 п‚і 1
k2
m пЂ« k1 пЂ« k 2
| vy |п‚і 1
m
m
a ... aa ... aa ... aa ... aa ... a bbb ... bbb ccc ...ccc
u
v
2
x
y
2
z
Prof. Busch - LSU
56
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
2
| vy |п‚і 1
2
From Pumping Lemma: uv xy z пѓЋ L
k1 пЂ« k 2 п‚і 1
2
2
However: uv xy z пЂЅ a
m пЂ« k1 пЂ« k 2
m
b c
m
пѓЏL
Contradiction!!!
Prof. Busch - LSU
57
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Case 2:
vxy
| vxy |п‚Ј m
is in b
| vy |п‚і 1
m
Similar to case 1
m
m
m
aaa ... aaa b ... bb ... bb ... b ccc ...ccc
u
vxy
Prof. Busch - LSU
z
58
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Case 3:
vxy
| vxy |п‚Ј m
is in c
| vy |п‚і 1
m
Similar to case 1
m
m
m
aaa ... aaa bbb ... bbb c ...cc ...cc ...c
u
Prof. Busch - LSU
vxy
z
59
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Case 4:
vxy
m
| vxy |п‚Ј m
overlaps
a
| vy |п‚і 1
m
m
and b
m
m
a ... aa ... aa b ... bb ... bbb ccc ...ccc
u
z
vxy
Prof. Busch - LSU
60
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Sub-case 1:
| vxy |п‚Ј m
| vy |п‚і 1
v contains only a
y contains only b
m
m
m
a ... aa ... aa ... a b ... bb ... bb ... b ccc ...ccc
u
v
x
y
Prof. Busch - LSU
z
61
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
v пЂЅa
k1
| vxy |п‚Ј m
y пЂЅa
m
| vy |п‚і 1
k1 пЂ« k 2 п‚і 1
k2
m
m
a ... aa ... aa ... a b ... bb ... bb ... b ccc ...ccc
u
v
x
y
Prof. Busch - LSU
z
62
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
v пЂЅa
k1
| vxy |п‚Ј m
y пЂЅa
| vy |п‚і 1
k1 пЂ« k 2 п‚і 1
k2
m пЂ« k2
m пЂ« k1
m
a ... aa ... aa ... a b ... bb ... bb ... b ccc ...ccc
u
v
2
x
y
2
Prof. Busch - LSU
z
63
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
2
2
From Pumping Lemma: uv xy z пѓЋ L
k1 пЂ« k 2 п‚і 1
However:
2
2
uv xy z пЂЅ a
m пЂ« k1 m пЂ« k 2 m
b
c
пѓЏL
Contradiction!!!
Prof. Busch - LSU
64
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
Sub-case 2: v contains a and b
y contains only b
m
m
m
a ... aa ... a b ... bb ... bb ... bb ... b ccc ...ccc
u
v
x
y
Prof. Busch - LSU
z
65
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
By assumption
k1
v пЂЅa b
k2
y пЂЅa
m
k1 , k 2 п‚і 1
k3
m
k2
k1
m
k3
a ... aa ... a b ... bb ... bb ... bb ... b ccc ...ccc
u
v
x
y
Prof. Busch - LSU
z
66
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
k1
v пЂЅa b
k2
| vxy |п‚Ј m
y пЂЅa
k1 , k 2 п‚і 1
k3
m пЂ« k3
m
| vy |п‚і 1
m
2k 3
k1
k 2 k1 k 2
a ... aa ... ab ... ba ... ab ... bb ... bb ... bb ... b ccc ...ccc
u
v
2
x
Prof. Busch - LSU
y
2
z
67
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
2
2
From Pumping Lemma: uv xy z пѓЋ L
k1 , k 2 п‚і 1
2
2
m
k2
k1
However: uv xy z пЂЅ a b a b
m пЂ« k3
c
m
пѓЏL
Contradiction!!!
Prof. Busch - LSU
68
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
| vxy |п‚Ј m
| vy |п‚і 1
Sub-case 3: v contains only a
y contains a and b
Similar to sub-case 2
m
m
m
a ... aa ... aa ... aa ... a b ... bb ... b ccc ...ccc
u
v
x
y
Prof. Busch - LSU
z
69
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Case 5:
vxy
| vxy |п‚Ј m
overlaps
b
| vy |п‚і 1
m
and c
m
Similar to case 4
m
m
m
aaa ... aaa bbb ... bbb ccc ... ccc
u
vxy
Prof. Busch - LSU
z
70
n n n
L пЂЅ { a b c : n п‚і 0}
m m m
wпЂЅa b c
w пЂЅ uvxyz
Case 6:
vxy
m
| vxy |п‚Ј m
| vy |п‚і 1
m
overlaps a , b
Impossible!
m
m
and c m
m
aaa ... aaa bbb ... bbb ccc ... ccc
u
vxy
Prof. Busch - LSU
z
71
In all cases we obtained a contradiction
Therefore: the original assumption that
n n n
L пЂЅ { a b c : n п‚і 0}
is context-free must be wrong
Conclusion:
L is not context-free
Prof. Busch - LSU
72
Документ
Категория
Презентации
Просмотров
3
Размер файла
1 254 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа