Consider the language $L = {a^{n} | n > 0} \cup {a^{n} b^{n} | n \geq 0}$ and the following statements.
I. L is determnistic 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?

Open in App

Solution

Statement I: L in DCFL is true, since ${a^{n}} \cup {a^{n} b^{n}}$ = regular $\cup$ DCFL = DCFL, by clouser property. So II is false and I is true.

Statement III is true because we cannot write LL(k) grammar, for any value of k, since no matter how many a's are shown to compiler it will be impossible to distinguish between whether the string presented is in the form of ${a^{n}} o r {a^{n} b^{n}}$ and hence the production cannot be chosen uniquely for any value of k.

So option (a) is correct, I and III only are true.

Suggest Corrections

Similar questions

L_{1} = {a^{p} | p i s a p r i m e n u m b e r}

L_{2} = {a^{n} b^{m} c^{2 m} | n \geq 0, m \geq 0}

L_{3} = {a^{n} b^{n} c^{2 n} | n \geq 0}

L_{4} = {a^{n} b^{n} | n \geq 1}

L_{1}

L_{2}

L_{3}

L_{4}

L_{1} L_{2}

L_{1} \cup L_{2}

_{1}

L_{1} - R

L_{1} \cap L_{2}

¯ L

¯ L

¯ L

Join BYJU'S Learning Program