GATE 2005-IT
March 19, 2025GATE 2007
March 20, 2025GATE 2007
| Question 30 |
The language L = {0i21i | i≥0} over the alphabet {0, 1, 2} is:
| not recursive. | |
| is recursive and is a deterministic CFL.
| |
| is a regular language.
| |
| is not a deterministic CFL but a CFL. |
Question 30 Explanation:
We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.
Correct Answer: B
Question 30 Explanation:
We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.