Calicut Gate Academy Test Series | TOC

Question

L={a^mbⁿc^kd^l  | (n-k ) is odd only if (m-l) is odd , m,n,k,l >=0 } is  best fit under which language class

1. RL
2. DCFL
3. CFL
4. CSL

Comments

Is it DCFL ?

Answer 1

The language can be further described systematically as :

(n-k) is odd fine..This means that either n or k will be odd since if both are even or odd then difference will be even..

Similar is the case for (m - l)..Hence we can redefine the language as :

L = { aⁱ b^j c^k d^l  | if(i is odd and l is even then  j is odd and k is even or vice versa }  U

     {  aⁱ b^j c^k d^l  | if(i is even and l is odd then  j is odd and k is even or vice versa }

Now each of the parts described can be done by finite automata and hence regular..

So L which is union of these parts is also regular [Also follows from the fact that union of regular langauges is regular]

So L is regular ..

Hence A) is the correct answer..