=========================preview======================
(COMP272)02qbank-sol.pdf
Back to COMP272 Login to download
======================================================
COMP272 Question Bank 2 Suggested Solution
Pumping Theorem for Regular Languages Question 1
a) We claim that it is not regular. Suppose, on the contrary, that it is regular. By the pumping theorem, there exists an integer n 1 (which is actually the number of states in the corre-sponding DFA) such that any string w L with |w| n can be written as
i
w = xyz such that (1) y .z L for each i 0.
= e, (2) |xy| n, and (3) xyConsider the string w = anba2n L. By the theorem, it can be rewritten as w = xyz such that the length of xy n and y .This implies that y can
= e. only lie within the region of the .rst consecutive as which means that the only possibility for y is
y = aj for some j> 0
Consider xz = an.jba2n. Since j> 0, thus an.jba2n is not in the form aiba2i; thus it is not in L. This contradicts with (3).
b) Observe that the language can be rewritten as: {(babbabbab)i : i 1}, which can be represented by the regular expression (babbabbab)(babbabbab). . Hence it is regular.
c) We claim that the language (denoted by L) is not regular. Suppose, on the contrary, that it is regular. Therefore the pumping theorem
nbn+1
will apply for some integer n 1. Consider the string w = a L. The pumping theorem says that there exists a decomposition of w = xyz
i
such that (1) y .e, (2) |xy| n, and (3) xyz L for each i 0. From =
(2) we know that the only possiblity is that y consists only of as, and from
q
(1), y must have at least one a; thus, we let y = awhere q> 0. So, let
pq rbn+1
x = a, y = aand z = awhere q> 0 and n = p + q + r. Consider
2p2qnbn+1 n+qbn+1
xyz = aaa= a. Since q 1 implies n + q n + 1, thus
22
xyz /L. This contradicts with (3) which implies xyz L. Therefore L is not regular.
d) Suppose, on the contrary, that L is regular. Then the Pumping theorem
n+1bn
applies for some integer n 1. Consider the string w = a L. The pumping theorem says that there exists a decomposition of w = xyz such that
i
(1) y .e, (2) |xy| n, and (3) xy= z L for each i 0. From (1) and (2),
q pq
the only possiblity for y is y = afor some q> 0. So, let x = a, y = a
n+1.qbn
and z = arbn, where p + q + r = n + 1. Consider, xy = a. Since q> 0 ..q< 0 . n +1 . q<n +1 . n +1 . q n, thus xy / L. This contradicts with (3). Therefore L is not regular.
Question 2
a) Suppose, on the contrary, that the language (denoted by L) is regular. There-fore pumping theorem applies for some n 1. Consider the string w = anbban L. By the theorem, it can be rewritten as w = xyz such that (1)
i
y .e, (2) |xy| n, and (3) xy L for each i 0. From (1) and (2), = z
p
y = aq, where q> 0. Let x = a, y = aq and z = arbban, where p + q + r = n. Consider xz = an.qbban . Since q> 0 ..q< 0 . n . q<n. Thus, xz is
1
not a palindrome, thus xz / L. This contradicts with (3). Therefore L is not regular.
b) Suppose, on the contrary, that the language (denoted by L) is regular.