Push Down Automata: CFL & DCFL GATE 1992 Question #8813 with Solution

GATE 1992

Theory of ComputationPush Down Automata: CFL & DCFLmediumMCQ2 marks

Which of the following statements about Chomsky Normal Form (CNF) is TRUE?

AAny derivation of a string of length n (n ≥ 1) requires exactly 2n - 1 stepsBEvery production must have 3 terminalsCIt allows ε-productions for all non-terminalsDIt parses strings in n^2 steps

Save your progress

Related Theory of Computation PYQs

GATE 1992

What is the minimum number of states in a DFA accepting the language L = {w ∈ {a, b}* | w contains both 'aa' and 'bb' as substring…

GATE 1992

Which of the following statements is TRUE about deterministic context-free languages (DCFLs)?

GATE 1992

What is the minimum number of states in a DFA over alphabet {a, b} accepting the language L = {w | w contains an even number of 'a…

GATE 1992

What is the minimum number of states in a DFA accepting the language L = {w ∈ {0, 1}* | w contains an odd number of 1s}?

GATE 1992

Which of the following languages is context-free?

GATE 1992

What is the minimum number of states in a DFA accepting the language L = {w ∈ {0, 1}* | w starts with '1' and ends with '0'}?

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