Homeworks on Context Free Language
------======
Presume Sigma={a,b}, unless stated otherwise
Write Push Down Automata for the following languages:
1. a^n b^n | n>=3
2. a^n b^(n+m) c^m | n,m>=0, sigma={a,b,c}
3. a^2n b^n | n>=0
4. Equal number of a's and b's (AHU: p241, exc 6.2c)
5. Work on the string 011 with the PDA for ww^r on slide 16
6. a^i b^j c^k, either i=j or j=k, not necessarily i=j=k but that is allowed
Homeworks on Context Free Language
------======
Presume Sigma={a,b}, unless stated otherwise
Write Push Down Automata for the following languages:
1. a^n b^n | n≥3
PDA: M = ({q1, q2, q3, q4, q5}, {a, b}, {#, A,B,C}, δ, q1, #, {})
δ:
(1)δ(q1, a, #) = {(q2, A#)}// push A when getting first a
(2)δ(q2, a, A) = {(q3, BA)}// push B when getting second a
(3)δ(q3, a, B) = {(q4, CB)} // push C when getting third a
(4)δ(q4, a, C) = {(q4, CC)} //push C when getting another a
(5)δ(q4, b, C) = {(q5, ε)}// popC on first b
(6) δ(q5, b, C) = {(q5, ε)}// pop C when getting b
(7)δ(q5, b, B) = {(q5, ε)}// pop B when getting b
(8)δ(q5, b, A) = {(q5, ε)}// pop A when getting b
(9)δ(q5, ε, #) = {(q5, ε)}// accept on end of string
2. a^n b^(n+m) c^m | n,m≥0, sigma={a,b,c}
Logic: 1) Push A's when getting a's, pop A's when getting same number of b's.
2) After balancing, start over again. 3) Then, push B's when getting more b's, pop B's when getting C's until the stack is empty. Make sure, n=0 but m=/=0, opposite, or n=m=0 are handled correctly.
PDA: M = ({q1, q2, q3}, {a, b,c}, {#, A,B }, δ, q1, #, {})
δ:
(1)δ(q1, a, #) = {(q1, A#)}// push A when getting first a
(2)δ(q1, a, A) = {(q1, AA)}// push A when getting a
(3)δ(q1, b, A) = {(q2, ε)} // popAon first b
(4)δ(q2, b, A) = {(q2, ε)} // popA when getting b
(5)δ(q1, b, #) = {(q3, B#)} // pushBon first char asb, n = 0
(6)δ(q2, b, #) = {(q3, B#)} //push Bon seeing extrab, after finishing a^n b^n
(7)δ(q2, ε, #) = {(q3, ε)}// accept on end of string, m=0
(8)δ(q3, b, B) = {(q3, BB)}// push B when getting b
(9)δ(q3, c, B) = {(q3, ε)}// pop B when getting c
(10)δ(q3, ε, #) = {(q3, ε)}// accept on end of string
(11)δ(q1, ε, #) = {(q3, ε)}// accept: null string, n=0 and m=0
Example:
1) a^2 b^(2+3) c^3 = aabbbbbccc
(q1, aabbbbbccc, #) |- Rule Applied
(q1, abbbbbccc, A#) |- (1)
(q1, bbbbbccc, AA#) |-(2)
(q2, bbbbccc, A#) |-(3)
(q2, bbbccc, #) |-(4)
(q3, bbccc, B#) |-(6)
(q3, bccc, BB#) |-(8)
(q3, ccc, BBB#) |-(8)
(q3, cc, BB#) |-(9)
(q3, c, B#) |-(9)
(q3, ε,#) |-(9)
(q3, ε, ε): accept(10)
2) a^2 b^(2+2) c = aabbbbc
(q1, aabbbbc, #) |- Rule Applied
(q1, abbbbc, A#) |- (1)
(q1, bbbbc, AA#) |-(2)
(q2, bbbc, A#) |-(3)
(q2, bbc, #) |-(4)
(q3, bc, B#) |-(6)
(q3, c, BB#) |-(8)
(q3, ε, B#): reject(9)
No more rules Applicable…
3. a^2n b^n | n≥0
Pop two A's when for each b.
PDA: M = ({q1, q2, q3, q4}, {a, b}, {#, A}, δ, q1, #, {})
δ:
(1)δ(q1, a, #) = { (q1, A#)}// push A when getting first a
(2)δ(q1, a, A) ={(q1, AA)}// push A when getting a
(3)δ(q1, b, A) = {(q3, ε)}// pop A when getting first b
(4)δ(q3, ε, A) = {(q2, ε)}// pop A without reading next b, balancing even numbered a on the left
(5)δ(q2, b, A) = {(q3, ε)}// pop A forodd numbered a in prefix
(6)δ(q2, ε, #) = {(q4, ε)}// accept on end of string, after balancing
(7)δ(q1, ε, #) = {(q4, ε)}// accept: null string, no a, and no b
4. Equal number of a's and b's (AHU: p241, exc 6.2c)
G: S→aSbS|bSaS|ε
Rules: 1) Starting character a/b decides what to push on stack B/G as the counter, 2) every time blancing is finished with #b’s = #a’s, start all over again, 3) if e is read on start (or restart) accept.
PDA: M = ({q1 ,q2, q3}, {a,b}, {#, B, G},δ,q1, #, {})
δ:
(1)δ(q1, a, #) = {(q2, B#)}// first symbol is a, push B
(2)δ(q1, b, #) = {(q3, G#)}// first symbol is b, push G
(3)δ(q1, ε, #) = {(q1, ε)}// accept
(4)δ(q2, a, B) = {(q2, BB)} // push B when getting another a
(5)δ(q2, b, B) = {(q2, ε)} //the stack is counting a's and, pop B when getting b
(6)δ(q2, ε, #) = {(q1, #)}//a’s and b’s matched, start again
(7)δ(q3, a, G) = {(q3, ε)}//the stack is counting b's and pop G when getting a
(8)δ(q3, b, G) = {(q3, GG)}// push G when getting another b
(9)δ(q3, ε, #) = {(q1, #)}//b’s and a’s matched, start again
Example:
1) ababba
(q1, ababba, #) |- Rule Applied
(q2, babba, B#) |- (1)
(q2, abba, #) |-(5)
(q1, abba, #) |-(6)
(q2, bba, B#) |-(1)
(q2, ba, #) |-(5)
(q1, ba, #) |-(6)
(q3, a,G#) |-(2)
(q3, ε,#) |-(7)
(q1, ε, ε): accept(9)
1) abbba
(q1, abbba, #) |- Rule Applied
(q2, bbba, B#) |- (1)
(q2, bba, #) |-(5)
(q1, bba, #) |-(6)
(q3, ba, G#) |-(2)
(q3, a, GG#) |-(8)
(q3, ε, G#) :reject (7)
No more rules Applicable…
5. Work on the string 011 with the PDA for ww^r on slide 16
δ:
Computation:
StateInputStackRule AppliedRules Applicable
q1011#(1)
q111B#(1)(5)
q11GB#(5)(6), both options
q2εGGB#(6) option #1-crashes, no-rule to apply-
And: (q2, ε, B#) by option#2 -rejects: end of string but not empty stack-
6. a^i b^j c^k, either i=j or j=k, not necessarily i=j=k but that is allowed
The PDA has a nondeterministic branch at q1.(either i=j or j=k)
PDA: M = ({q1,q2, q3,q4}, {a,b,c}, {#, A, B},δ, q1, #, {})
δ:
(1)δ(q1, a, #) = {( q1, A#)}// push A when getting a
(2)δ(q1, a, A) = {( q1, AA)} // push A when getting a
(3)δ(q1, ε, A) = {( q1, ε)} // pop A when no b and no c, (j=k=0)
(4)δ(q1, b, A) = {( q2, ε), (q3, BA)}// pop A when gettingb(i=j) , option#1
or push B when getting b(j=k) , option#2
(5)δ(q2, b, A) = {(q2, ε)}// popA when getting b
(6)δ(q1, b, #) = {(q3, B#)}// push B on first character as b, i=0
(7)δ(q2, c, #) = {(q2, #)}// after b’s balanced to a’s (i=j),ignore c’s
(8)δ(q1, c, #) = {(q2, #)}// when getting only c’s(i=j=0)
(9)δ(q2, ε, #) = {(q4, ε)}// accept
(10)δ(q3, b, B) = {(q3, BB)}// push B when getting b (for j=k)
(11)δ(q3, c, B) = {(q4, ε)}// pop B when getting c, change state to make sure more b’s or a’s are not allowed
(11’)δ(q4, c, B) = {(q4, ε) }// pop B when getting c
(12)δ(q4, ε, A) = {(q4, ε)}// pop A’s, after checking j=kignore prefix a’s
(13)δ(q4, ε, #) = {(q4, ε)}// accept
(14)δ(q1, ε, #) = {(q4, ε)}// accept: null string, no a, no b, and no c