Brett Bernstein – From Kozen’s Book
page 336
84.
a) CFL
S → T | AU
T → aaaTcc | aaaBcc
U → bbbbbUccccccc | bbbbbccccccc
A → aA | A
B → bB | b
b) Not a CFL
z =
If the devil picks only b’s to pump on (puts them in v and x) we can break the second equality by pumping up. If the devil picks a’s to pump on, he cannot also pick c’s so we can break the first equality by pumping up. The same argument works with picks c’s and the inability to also pump on a’s.
c) CFL
S → TC | U //Choose the first or second condition respectively
T → Q | R //Choose n<3m or n>3m respectively
Q → aaaQb | aaaBb | aB | aaB //Accepts n<3m
R → aaaRb | aaaAb //Accepts n>3m
U → M | N //Choose n<5k or n>5k respectively
M → aaaaaMc | aaaaaBCc | aBC | aaBC | aaaBC | aaaaBC //Accepts n<5k
N → aaaaaNc | aaaaaABc //Accepts n>5k
A → aA | a //Accepts a+
B → bB | b //Accepts b+
C → cC | c //Accepts c+
For those who understand machines better (question asked for grammar though):
Build a machine that will first non-deterministically choose whether to accept based on the first “or condition” or the second. If the first is chosen, non-deterministically decide whether n < 3m or n > 3m. n > 3m is accepted by:
1)Non-deterministically skip a positive number of a’s in the input
2)For all a’s push ‘A’ on the stack (must be at least 1 a)
3)At a ‘b’ start popping 3 A’s at a time for each b (how do you pop 3?)
4)Eat all c’s and accept on empty stack (must be at least 1 c)
n < 3m is accepted by:
1) For all a’s push ‘A’ on the stack (must be at least 1 a)
2) At a ‘b’ start popping 3 A’s at a time for each b
3) Non-deterministically choose a point to pop 0, 1, or 2 A’s from the stack for a b
4)Eat all b’s then c’s and accept on empty stack(must be at least 1 c)
The same process works of the second condition except:
1)5 is the number instead of 3
2)You are dealing with the outer a’s and c’s instead of a’s and b’s
3)The eating of c’s before is replaced by the eating of b’s that occur after the “a-pushing phase”
d*) Not a CFL
This problem requires us to use a more powerful version of the Context-Free pumping lemma called Ogden’s Lemma.
Ogden’s Lemma:
Demon picks n > 0
You pick such that |z| n
You pick at least n symbols in z to be “distinguished”
Demon picks vwx such that:
vwx has at most n symbols
vx has at least 1 symbol
You pick i such that uviwxiy
Proof:
z =
All b’s are distinguished.
Case 1: Demon picks a’s
Then the demon can’t pick any c’s since it would force vwx to contain more than n distinguished positions. Thus we pump the number of a’s till it is equal to m+m! (always possible) breaking the second condition.
Case 2: Demon doesn’t pick a’s
Pump the number of b’s till it is equal to 5n+(5n)! (always possible) breaking the first condition.
e) CFL
Method 1 (required since question asked for Grammar):
S → TU
T → aTb | ab
U → bUc | bc
Method 2 (closure):
=
This is the concatenation of anbn with bmcm and is thus a CFL.
f) CFL
Method 1 (required since question asked for Grammar):
S → TU
T → aTb | ab
U → cUd | cd
Method 2 (closure):
=
This is the concatenation of anbn with bmcm and is thus a CFL.
g) Not a CFL
z = akbkckdk
If the demon pumps on a’s, b’s, c’s, or d’s then he cannot pump on c’s, d’s, a’s or b’s respectively. This fact allows us to pick a pumping value that will break one of the equalities every time.
h) CFL
S → aSd | aTd
T → bTc | bc
85.
a) Not a CFL
Method 1:
z = akbkck
If demon pumps on a’s, b’s or c’s he cannot also pump on c’s, a’s and c’s, or a’s respectively. This will break the condition.
Method 2:
Intersect with a*b*c* producing anbncn which is not a CFL.
b) Not a CFL
Method 1:
z =
Demon must pump on an area whose length is anywhere between 1 and k inclusive. 2k < 2k+1 2k+k < 2k+1 for all k1. The k = 0 case is not handled but is finite and thus doesn’t damage our proof.
Method 2:
Corollary to Parikh’s Theorem states:
Any language on {a}* that isn’t regular isn’t context-free.
By a proof equivalent to that in Method 1 we can prove this language isn’t regular and thus isn’t context free either.
c) = L(0*10*) Regular
d) L(a*b*c*) Regular
e) The set of all balanced strings of parentheses of three types, ( ) [ ] { } CFL
Not Regular Proof Method1:
Intersection with L( [* ]*) gives you [n]n which is not regular.
Not Regular Proof Method 2:
s = xyz = [k]k where x = [k y = ]k and z = ε
y = uvw, |y| = |u|+|v|+|w| = i+j+k
Let i = 2: s = xuv2wz = [k]k+j the language
Not Regular Proof Method 3:
Ai = = the equivalence class of {i
since {i}i is in the language and {i}j isn’t
CFL Proof:
S → (S) | [S] | {S} | SS | ε
f) A=CFL
Not regular:
~AL(a*b*) = anbn
CFL proof:
S → aSb | A | B
A → aA | a
B → bB | b
g) CFL
Not regular:
s = xyz = a3kc2kd, x = a3k, y = c2k, z = d
y = uvw, |y| = |u|+|v|+|w| = i+j+k
Let i = 2: xuv2wy = a3kc2k+jd which is not in the language
CFL proof:
S → RD | AT
R → aaaRcc | B
T → bbbbbbbTddddd | C
A → aA | ε
B → bB | ε
C → cC | ε
D → dD | ε
h) Not a CFL
Not a CFL:
z = a3kb7kc2kd5k
If the demon pumps on a’s, b’s, c’s or d’s respectively he cannot pump on c’s, d’s, a’s, or b’s respectively and thus will break one of the equalities.
i) CFL
Not regular:
s = xyz = a3kb2k, x = a3k, y = b2k, z = ε
y = uvw, |y| = |u|+|v|+|w| = i+j+k
Let i = 2: xuv2wy = a3kb2k+j which is not in the language
CFL proof:
S → RT
R → aaaRbb | ε
T → cccccccTddddd | ε
j) CFL
Not regular:
s = xyz = a3kd2k, x = a3k, y = d2k, z = ε
y = uvw, |y| = |u|+|v|+|w| = i+j+k
Let i = 2: xuv2wy = a3kd2k+j which is not in the language
CFL proof:
S → aaaRdd | T
T → bbbbbTccccccc | ε
k) Not a CFL
Not a CFL:
z = ak+2bk+1ck
If you pick any a’s pump down breaking either the inequality on b or c. If you pick any c’s pump up breaking the inequality on b’s or a’s. If you pick only b’s pump up breaking the inequality on a’s.
l) CFL
Not regular:
s = xyz = ak+1bkc2k, x = ak+1, y = bk, z = c2k
y = uvw, |y| = |u|+|v|+|w| = i+j+k
Let i = 2: xuv2wy = ak+1bk+jc2k which is not in the language
CFL proof:
S → RC | AT
R → aRb | aA
T → bTc | bB
A → aA | ε
B → bB | ε
C → cC | ε
m) A = CFL
Not regular:
h(a) = b, h(b) = a
Problem (f)
CFL proof:
Method 1:
S → ASb | bSA | SS | A
A → aA | a
Method 2:
Build a machine that accepts on empty stack:
1) With the start symbol on top of the stack, given an input of ‘a’ it pushes A and given ‘b’ it pushes B on the stack never erasing the start symbol
2) If A is on the top of the stack it pushes another A on ‘a’ or pops the A on ‘b’
3) If B is on the top of the stack it pushes another B on ’b’ or pops the B on ‘a’
4) Can non-deterministically pop an A or AS from the stack where S is the Start symbol (how to pop AS?)
n) = Finite = Regular
o) CFL
Not regular:
s = xyz = a6k+6b10k+2, x = a6k, y = bk, z = b9k+2
y = uvw, |y| = |u|+|v|+|w| = i+j+k
y = xuv2wy = a6kb10k+2+j which isn’t in the language
CFL proof:
S → aaaSbbbbb | aaaaaabb