Theory-of-Computation
October 6, 2023GATE 2020
October 6, 2023GATE 2020
| Question 13 |
Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.
- I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
| II only | |
| III only | |
| I only | |
| I and III only |
Question 13 Explanation:
L is DCFL.
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Correct Answer: D
Question 13 Explanation:
L is DCFL.
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.