GATE Computer Science (CS) 2020 Solved Papers

Question : 29 of 65

Marks: +1, -0

Consider the language

{L}=\{ {a}^{n} ∣ {n} ≥ 0\} ∪\{ {a}^{ {n}} {b}^{ {n}} ∣ {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?

III only
I and III only
I only
II only

Validate

Solution:

Statement I- -

\table {L}=\{ {a}^{ {n}} ∣ {n} ≥ 0\} ,∪\{ {a}^{ {n}} {b}^{ {n}} ∣ {n} ≥ 0\}; ↓ , ↓ ;\Linear \power, \well \know \DCFL

∴ it is regular
∴ L = Regular ∪ DCFL {use the closure properties}
L = DCFL
Statement--III As we cannot write LL( k ) grammar, for any value of k, Hence statement III is correct.

Go to Question:

Prev Question

Next Question