Use the pumping lemma to show that the following languages are
not regular.
A a. A1={0^n 1^n 2^n | n≥0}
b. A2 = {www | w ∈ {a,b}∗}
A c. A3 ={a^2^n | n≥0} (Here, a^2^n means a string of 2^n
a’s.)
A ={a3n |n > 0 }
Use the pumping lemma to show that the following languages are
not regular
(c) (5 pts) Let Σ = {0, 1, −, =} and
SUB = {x = y − z | x, y, z are binary integers, and x is the
result of the subtraction of z from y}. For example: 1 = 1 − 0, 10
= 11 − 01 are strings in SUB but not 1 = 1 − 1 or 11 = 11 − 10.
Use the pumping lemma to prove that the following languages are
not regular.
(a)L2 = {y = 10 × x | x and y are binary integers with no
leading 0s, and y is two times x}. (The alphabet for this languages
is {0, 1, ×, =}.) For example, 1010 = 10 × 101 is in L2, but 1010 =
10 × 1 is not.
(b)Let Σ2 = {[ 0 0 ] , [ 0 1 ] , [ 1...
1. Pumping Lemma:
a. Is the following language a regular language? (Use pumping
lemma in proof.) L = {0n 1n 2n | n ≥ 0}
b. What is (i.e., define) the CFL pumping lemma?
Do not use Pumping Lemma for Regular Expression to prove the
following. You may think of Closure Properties of Regular
Languages
1. Fix an alphabet. For any string w with |w| ≥ 2, let middle(w)
be the string obtained by removing the first and last symbols of w.
That is, Given L, a regular language on Σ, prove that f1(L) is
regular, where
f1(L) = {w : middle(w) ∈ L}
Use Context-Free Pumping
Lemma to prove that that following languages over the alphabet
{'x', 'y', 'z'} are NOT context-free
(a)
{xjy2jzj
: j > 0}
(b) {
xmynzk
: m, n, k ≥ 0 and k = min(m,n) }