GATE 2005
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable.
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…
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?
Let L be the set of all binary strings ending with 01. Which of the following regular expressions generates L?
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.