TheoryofComputation
October 6, 2023TheoryofComputation
October 6, 2023TheoryofComputation
Question 5

Consider the language L = {a^{n} n≥0} ∪ {a^{n}b^{n} n≥0} and the following statements.
 I. L is deterministic contextfree.
II. L is contextfree but not deterministic contextfree.
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 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.
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 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.
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.
Subscribe
Login
0 Comments