test series

Question

L1 = {a^mb^nc^p | m ≥ n or n = p}
L2 = {a^mb^nc^p | m ≥ n and n = p}

(a) Both are NCFL’s
(b) L1 is DCFL and L2 is NCFL
(c) L1 is NCFL and L2 is not context-free
(d) Both are not context-free
Solution: Option (c)

how it is possible plz explain indetail

Comments

Option c and d are same right? :o

---

nope

---

Both the options say that they L1 and L2 are ncfls.

---

option c says L1 is non determinstic context free language and L2 is determinstic cfl

option d says both L1 and L2 are non cfl

---

L1 NCFL

L2 CSL

---

plz explain brifely

---

@navya n

L1 requires only one comparission at a time ===>CFL, due to Ambiguity it is Non-Deterministic CFL

L2 requires two comparissions at a time ===> CSL

---

Oh yes..sorry .I read it wrongly..

Option C says L1 is ncfl and L2 is not CFL

---

How L1 becomes NCFL? can anybody give PDA for it?

---

There are two possibilities

1) m>=n                                  2) n=p

For 1) first push a then pop 1 a for each b. Since m>=n so it might happen that there are still some a's left after all b's are exhausted.

 For the remaining c's we don't need to do anything

For 2) Do nothing when we get a and push all b's and pop each b for each c.

 

 

---

Thanks @MNIPanda, I really appreciate your help.