Push Down Automata: CFL & DCFL GATE 2021 Question #705 with Solution

GATE 2021 · Set-2

Theory of ComputationPush Down Automata: CFL & DCFLhardMSQ2 marks

For a string w, we define \(w^{R}\) to be the reverse of w. For example, if w = 01101 then \(w^{R}\) = 10110. Which of the following languages is/are context-free?

A{w x \(w^{R}\) \(x^{R}\) | w, x in {0,1}*}B{w \(w^{R}\) x \(x^{R}\) | w, x in {0,1}*}C{w x \(w^{R}\) | w, x in {0,1}*}D{w x \(x^{R}\) \(w^{R}\) | w, x in {0,1}*}

Select every correct option.

Save your progress

Related Theory of Computation PYQs

GATE 2021 · Set-1

Suppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily c…

GATE 2021 · Set-1

Let <M> denote an encoding of an automaton M. Suppose that Σ = {0,1}. Which of the following languages is/are NOT recursive?

GATE 2021 · Set-1

For a Turing machine M, <M> denotes an encoding of M. Consider the following two languages. L1 = {<M> | M takes more than 2021 ste…

GATE 2021 · Set-1

The number of strings of length 100 accepted by the below pushdown automaton is _______________.

GATE 2021 · Set-2

Let L be a subset of {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following l…

GATE 2021 · Set-2

Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?

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.

Related Theory of Computation PYQs

Turn practice into measurable progress