MadeEasy Test Series: Theory Of Computation - Identify Class Language

Question

• Finite language
• Regular
• DCFL
• CFL but not DCFL

Acc. to solution c) but I think the answer should be b). Here's the reasoning:

We're looking for 

anbmcn $\cap$  axby  (x not equal to y)

=> bm  $\cap$ bn (n not equal to 0).

Comments

DCFL ?

Answer 1

Language generated by $L_1 = \big \{ \epsilon, ac,aacc,aaaccc, \dots,abc,aabcc,aaabccc, \dots, abbc, aabbcc, \dots, \;so\;on\big\}$

and $L_2 = \big \{\epsilon, ab,aabb,aaabbb,aaaabbbb, \dots \big \}$

And $L = L_1 - L_2$ is set difference. Means $L$ contains all strings that are in $L_1$ but not in $L_2$, which is clearly $L_1 - \epsilon$ ( as $\epsilon$ is only common string)

So, $L_1 - L_2 = \big \{ a^nb^mc^n\; |\; m,n \ge 0\big \} - \epsilon$, which is clearly DCFL.