Skip to content
GATEiit

GATE CSE 2020 Q20: Is {a^n} ∪ {a^n b^n} deterministic context-free or LL(k)?

Question

Consider the language L={an∣n≥0}∪{anbn∣n≥0}L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\} and the following statements.

I. LL is deterministic context-free.

II. LL is context-free but not deterministic context-free.

III. LL is not LL(kk) for any kk.

Which of the above statements is/are TRUE?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2020 final answer key)

Concept used: A DPDA can postpone the choice until it sees a b or the end; an LL(k) parser must decide after a bounded lookahead.

First step: Build a DPDA: push a's, and accept if input ends or if the following b's pop the stack exactly. Then ask how far ahead an LL parser must look for ana^n with large nn.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2020 questions →