Push Down Automata: CFL & DCFL GATE 2019 Question #1419 with Solution

GATE 2019

Theory of ComputationPush Down Automata: CFL & DCFLhardMCQ2 marks

Which one of the following languages over Σ = {a, b} is NOT context-free?

A{ w w^R | w ∈ {a, b}* }B{ w a^n b^n w^R | w ∈ {a, b}*, n >= 0 }C{ w a^n w^R b^n | w ∈ {a, b}*, n >= 0 }D{ a^n b^i | i ∈ {n, 3n, 5n}, n >= 0 }

Related Theory of Computation PYQs

Consider the following sets: S1: Set of all recursively enumerable languages over {0, 1}. S2: Set of all syntactically valid C pro…

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}. For string x = x1 x2 ... xn, let π(x) = x1 ∘ x2 ∘ ... ∘ xn. Co…

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

For Σ = {a, b}, let us consider the regular language L = { x | x = a^(2 + 3k) or x = b^(10 + 12k), k >= 0 }. Which one of the foll…

Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S → aSbS | bS | ε Which of the follo…

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be …

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.