Design PDAs that recognize the following languages. (a) L1 = {0^n1^n| n greatert

Question

Design PDAs that recognize the following languages. (a) L1 = {0^n1^n| n greaterthanorequalto 0} (b) L2 = (a^nb^mC^n| n, m greaterthanorequalto 0} (c) L3 = {a^nb^2n| n greaterthanorequalto 0} Show that the following languages are not context free (a) L1 = {a^nb^nc^n|n greaterthanorequalto 0} (b) L2 = {a^3k b^2k c^k elementof {a, b, c} * | k greaterthanorequalto 0} (c) L3 = {ab^kab^kab^k elementof {a, b} * | k greaterthanorequalto 0} (d) L4 = {a^k+mb^ka^mb^k elementof {a, b} * | k greaterthanorequalto 0, m greaterthanorequalto 0}

Explanation / Answer

1 (a): L1 = { 0n1n | n>=0 }

M = ({q0, q1}, {0, 1}, {L, $}, , q0, $, Ø)

:

(1) (q0, 0, $) = {(q0, L$)}   // Order of stack

(2) (q0, 1, $) = Ø        // Rejected

(3) (q0, 0, L) = {(q0, LL)} // Push L for each 0

(4) (q0, 1, L) = {(q1, )}    // Move to q1 on encounter of 1

(5) (q1, 1, L) = {(q1, )}

(6) (q1, , $) = {(q1, )}    //if read & $ hits accept

(7) (q1, , L) = Ø    // $ not reached, rejected

(8) (q0, , $) = {(q1, )}    // n=0, accept

Strings accepted = { , 01, 0011, 000111, ----}

Proof :

i) 0011

=> (q0, 0 011, $)

=> (q0, 0 11, L$)

=> (q0, 1 1, LL$)

=> (q1, 1, L$)

=> (q1, , $)

=> (q1, , ) => accept

ii) 011

=> (q0, 0 11, $)

=> (q0, 1 1, L$)

=> (q1, 1, $)

=> Ø => reject

https://drive.google.com/open?id=0B8AenggGjQqwY2hfRHcwdG5RT1FTSEp4YU10MENXbm5oTFhN

1 (b): L2 = { anbmcn| m,n>=0 }

M = ({q0, q1, q2}, {a, b, c}, {L, $}, , q0, $, Ø)

:

(1) (q0, a, $) = {(q0, L$)}

(2) (q0, b, $) = {(q1, $)}

(3) (q0, a, L) = {(q0, LL)}

(4) (q0, , $) = {(q1, $)}   

(5) (q1, b, $) = {(q1, $)}

(6) (q1, b, L) = {(q1, L)}

(7) (q1, , L) = {(q2, L)}

(8) (q1, c, L) = {(q2, )}

(9) (q1, c, L) = {(q2, )}

(10) (q2, , $) = {(q2, )}

Strings accepted = { , abbc, aabcc, aaabbccc, ----}

https://drive.google.com/open?id=0B8AenggGjQqwY2hfRHcwdG5RT1FTSEp4YU10MENXbm5oTFhN

1 (c): L3 = { anb2n | n>=0 }

M = ({q0, q1}, {a, b}, {L, $}, , q0, $, Ø)

:

(1) (q0, a, $) = {(q0, LL$)}   // Order of stack

(2) (q0, b, $) = Ø        // Rejected

(3) (q0, a, L) = {(q0, LLL)} // Push L for each 0

(4) (q0, b, L) = {(q1, )}    // Move to q1 on encounter of 1

(5) (q1, b, L) = {(q1, )}

(6) (q1, , $) = {(q1, )}    //if read & $ hits accept

(7) (q1, , L) = Ø    // $ not reached, rejected

(8) (q0, , $) = {(q1, )}    // n=0, accept

Strings accepted = { , abb, aabbbb, aaabbbbbb, ----}

Proof :

i) abb

=> (q0, a bb, $)

=> (q0, b b, LL$)

=> (q1, b, L$)

=> (q1, , $)

=> (q1, , ) => accept

ii) ab

=> (q0, a b, $)

=> (q0, b, LL$)

=> (q1, , L$)

=> Ø => reject

https://drive.google.com/open?id=0B8AenggGjQqwY2hfRHcwdG5RT1FTSEp4YU10MENXbm5oTFhN

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---