GATE 2005
Let L be the language recognized by the regular expression (a + b)* a (a + b)* a (a + b)*. What is the minimum number of states in a DFA that accepts L?
Related Theory of Computation PYQs
Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, lang…
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is…
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable.
Which of the following statements is TRUE about the language L = {a^n b^n | n >= 0}?
If a language L and its complement L' are both recursively enumerable (RE), then L is:
Which of the following problems is Turing-decidable?
Free account benefits
Turn practice into measurable progress
Public PYQs and reference pages stay free. Sign in when you want GATEverse to remember what you studied and guide what to practise next.
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.