GATE 2009
Let L1 be a recursive language and L2 be a recursively enumerable but not recursive language. Which of the following is definitely TRUE?
Related Theory of Computation PYQs
Let L= L1 ∩ L2 , where L1 and L2 are languages as defined below: L1={am bm cn bn | m,n >=0} L2={ai bj ck | i,j,k >=0} Then is L
Which one of the following languages over the alphabet {0, 1} is described by the minimal DFA with the fewest number of states?
What is the minimum number of states in a DFA over {a, b} that accepts all strings containing an even number of a's and an odd num…
Let L1 be a regular language and L2 be a non-regular language. Which of the following statements is ALWAYS TRUE?
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 …
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.