![GATE 2014 [Set-3]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
GATE 2014 [Set-3]
April 2, 2025GATE 2014 [Set-3]
April 2, 2025GATE 2014 [Set-3]
| Question 46 |
Consider the following languages over the alphabet Σ = {0,1,c}:
- L1 = {0n1n | n≥0}
L2 = {wcwr | w∈{0,1}*}
L3 = {wwr | w∈{0,1}*}
Here, wr is the reverse of the string . Which of these languages are deterministic Context-free languages?
| None of the languages | |
| Only L1 | |
| Only L1 and L2 | |
| All the three languages |
Question 46 Explanation:
L1 and L2 are DCFL, as we can design DPDA for them. For L1, DPDA will first push all zero’s in stack and when one appears in string, it will pop zero for every one and at the end if input string as well as stack is empty then accept the string else reject the string. Similarly for L2, DPDA will push all the string till it encounter the terminal “c” and once “c” appears in string, DPDA will ignore this “c” and then for every terminal in string (after “c”) it will pop one symbol from stack and match, if matched then pop next and continue. If didn’t match at any stage then reject the string. Since push and pop is clearly defined (i.e., every transition is deterministic), so both L1 and L2 is DCFL.
But in L3, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L3 is not possible. It can be accepted by NPDA only, so L3 is CFL but not DCFL.
Correct Answer: C
Question 46 Explanation:
L1 and L2 are DCFL, as we can design DPDA for them. For L1, DPDA will first push all zero’s in stack and when one appears in string, it will pop zero for every one and at the end if input string as well as stack is empty then accept the string else reject the string. Similarly for L2, DPDA will push all the string till it encounter the terminal “c” and once “c” appears in string, DPDA will ignore this “c” and then for every terminal in string (after “c”) it will pop one symbol from stack and match, if matched then pop next and continue. If didn’t match at any stage then reject the string. Since push and pop is clearly defined (i.e., every transition is deterministic), so both L1 and L2 is DCFL.
But in L3, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L3 is not possible. It can be accepted by NPDA only, so L3 is CFL but not DCFL.