Made Easy test

Question

which of the below are CFL:

a. L1 ={a^i b^j c^k |( i<=j or j<=i), j=k}

b.L2 = {a^m b^nc^n d^m  | m is not equals to n}

whether CFL or DCFL....please explain

Answer 1

1. L1 ={aⁱ b^j c^k |( i<=j or j<=i), j=k} : i and j may be any number i,e. there is no relation between i and j.  i<=j or i>=j. this condition will be always true.​​​​​​​  Only comparison is between j and k so it is DCFL.

2. L2 = {a^m bⁿ cⁿ d^m  | m is not equals to n}: First we have to compare between m and n of a^m, bⁿ. Then compare no of b and c, i,e. we require n from bⁿ to compare n from cⁿ. but we have lost exact no of n of b during the comparison of m and n. So it is NOT CFL. 

Answer 2

a) as i<=j and j<=i this concludes  that i>j or i<j or i=j so we have no relation but the other relation j=k alone is sufficient to prove that is  so the language L1= a^ib^jc^k hence we can more than one transitions for one state so it is dcfl  

b) as in this case we can remove b with c as there numbers are equal and a with d hence one transition exists here so it is DCFL

Comments

a)

L1 ={a^i b^j c^k |( i<=j or j<=i), j=k}

here only condition is j=k which makes it DCFL.

---

@kunal why you have not considered i=j here?? how DCFL?

---

just ignore this comment i got my point cleared...

---

@ANWER_ZAKI

I got your point...but in 2nd it is not DCFL, but how u decide whether CFL or not??

can't we do it using non deterministic PDA?