October 6, 2023
October 6, 2023
October 6, 2023
###### Theory-of-Computation
October 6, 2023
 Question 5

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?

 A II only B III only C I only D I and III only
Question 5 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.
Question 5 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.