Tutorial 2
Theory of Computation
呂紹甲
(Lu Shao-chia)
10/23
1
Overview
Pumping lemma
Homework 2
2
Review of Pumping Lemma
If A is a regular language, then there is a
number p (the pumping length) where, if s is
any string in A of length at least p, then s
may be divided into three pieces, s=xyz,
satisfying the following conditions:
1. for each i≧0, xy z ∈A
i
2. |y|＞0, and
3. |xy|≦p
3
Example (What’
s wrong?)
Prove that the language B ={0n1n|n≧0} is
not regular
Proof:
Consider s = 0p1p = xyz what is p?
So, if y = 0, xyyz = 0p+11p which is not in B
Thus, by pumping lemma, B is non-regular
4
Example (What’
s wrong?)
Prove that the language B ={0n1n|n≧0} is
not regular why B has
Proof: pumping length??
Let p be the pumping length of B
Consider s = 0p1p = xyz
So, if y = 0, xyyz = 0p+11p which is not in B
Thus, by pumping lemma, B is non-regular
5
Example (What’
s wrong?)
Prove that the language B ={0n1n|n≧0} is
not regular
Proof:
Assume B is regular. Let p be the pumping
length of B
Consider s = 0p1p = xyz what is xyz?
So, if y = 0, xyyz = 0p+11p which is not in B
Thus, by pumping lemma, B is non-regular
6
Example (What’
s wrong?)
Prove that the language B ={0n1n|n≧0} is
not regular
Proof:
Assume B is regular. Let p be the pumping
length of B. Consider s = 0p1p.
Let s be divided into 3 parts such that s = xyz
So, if y = 0, xyyz = 0p+11p which is not in B
Thus, by pumping lemma, B is non-regular
y=0? How about
other cases of y? 7
Example (What’
s wrong?)
Assume B is regular. Let p be the pumping
length of B. Consider s = 0p1p.
Let s be divided into 3 parts such that s = xyz
If y = 0k for some 1≦k ≦p, then xyyz =
0p+k1p which is not in B
Thus, by pumping lemma, B is non-regular
y=0k? How about other cases of y?
Currently, y can be any substring of s
8
Example (Good enough?)
Assume B is regular. Let p be the pumping
length of B. Consider s = 0p1p.
Let s be divided into 3 parts such that s = xyz
with |y| > 0, |xy| ≦p
So, y must be 0k for some 1≦k ≦p. Then
xyyz = 0p+k1p which is not in B
Thus, by pumping lemma, B is non-regular
Almost perfect… But we must show s is
in B to apply pumping lemma!
9
Example (Perfect Proof)
Assume B is regular. Let p be the pumping
length of B. Consider s = 0p1p, which is
obviously in B, and |s| is at least p.
Let s be divided into 3 parts such that s = xyz
with |y| > 0, |xy| ≦p
So, y must be 0k for some 1≦k ≦p. Then
xyyz = 0p+k1p which is not in B
Thus, by pumping lemma, we observe a
contradiction
Thus, we conclude that B is non-regular
10
Homework 2
1. Completing a proof (Easy)
2. Finding CFG (Moderate)
3. CFG CNF (Straightforward)
4. Finding CFG or PDA (Hard)
5. Pumping lemma (Easy)
11
Question 2(b)
Find CFG for:
{x1#x2#...#xk | k≧1, each xi ∈{a, b}*, and
for some i and j, xi=xjR }
Attention:
We need to allow for the case when i=j.
That is, some xi is a palindrome. Also,εis in
the language since it is a palindrome.
12
Question 4
Let C={x#y| x,y∈{0,1}* and x≠y}.
Show that C is a context-free language.
Hint: We can find CFG or PDA for this.
One observation is that: if s is in C, either
Case 1. |x| ≠ |y| (easy to generate)
or Case 2. The ith char of x is different from
the ith char of y (need thinking)
13
Homework 2: Further Studies
6. Properties of CFG
7. Application of Question 6
8. Proving Non-CFG (Hard)
14
Thank you
15