edited by
693 views
5 votes
5 votes
Which of the following is CFL?

1. $L=\{a^{m}b^{n}c^{p}d^{q}|m+q=n+p\}$

2.$L=\{a^{m}b^{n}c^{p}d^{q}|m+p=n+q\}$

Please also describe the logic of PDA.
edited by

1 Answer

Best answer
4 votes
4 votes
1. is a DCFL

See here we donot know the value of m,n,p,q. So, first start pushing a, then pop a by b. After poping all a's if more a remain in stack, start pushing b and then push c. After that when d comes in stack start poping until queue becomes empty.

2. is a DCFL

Here push a, Now pop a by b. If there are more number of b than a, then after poping all a's remaining b should be push into the stack. Now, when c comes start poping b by c and after poping all b's if more c remain start pushing those c's. Then d comes and pop all remaining c's
selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
practicalmetal asked Mar 15, 2023
496 views
Is the following language context free:The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.