Start learning →

GATE CSE Theory of Computation — practice questions

Explore 14 free Theory of Computation questions in GATE CSE Computer Science. Open each question or exercise to read its content, reference answers and available explanation.

Practise Theory of Computation with Quill →

Theory of Computation questions and exercises with answers

Showing questions 1–14 of 14.

A DFA accepts an input string $w$ if and only ifRead the answer and worked solution →An NFA with $n$ states can be converted to an equivalent DFA. The resulting DFA has AT MOST how many states?Read the answer and worked solution →Which language is REGULAR (recognised by some DFA)?Read the answer and worked solution →The REGULAR EXPRESSION $(0 + 1)^* 0$ describes the language of all strings over $\{0, 1\}$Read the answer and worked solution →Regular languages are CLOSED under which operations?Read the answer and worked solution →Which of these is an example of an IRREGULAR (non-regular) language?Read the answer and worked solution →Consider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated isRead the answer and worked solution →A CFG is AMBIGUOUS ifRead the answer and worked solution →Context-free languages are RECOGNISED by which type of machine?Read the answer and worked solution →The CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isRead the answer and worked solution →Every regular language is also context-free. The PROOF construction isRead the answer and worked solution →Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isRead the answer and worked solution →Which of the following languages is CONTEXT-FREE?Read the answer and worked solution →Which class of grammars generates ALL recursively enumerable languages?Read the answer and worked solution →

Worked practice questions

A DFA accepts an input string $w$ if and only if

  1. the computation visits every state at least once
  2. the input contains an even number of zeroes
  3. the computation halts before reading all of $w$
  4. computation ends in an accepting state
Show answer and solution

Correct answer: D. computation ends in an accepting state

1. A DFA's computation on input $w = w_1 w_2 \ldots w_n$: - Start in $q_0$ - For each symbol $w_i$, transition: $q_{i} = \delta(q_{i-1}, w_i)$ - End in state $q_n$ after reading all symbols 2. ACCEPTANCE: the DFA accepts $w$ iff $q_n \in F$. 3. The LANGUAGE of $M$ is $L(M) = \{w \mid M \text{ accepts } w\}$. Languages recognised by DFAs are precisely the REGULAR LANGUAGES. 4. Options A, C, D are wrong or unrelated criteria for acceptance. _Source: Jeff Erickson, "Models of Computation", §2.4 (Acceptance condition)._

Open this question →

An NFA with $n$ states can be converted to an equivalent DFA. The resulting DFA has AT MOST how many states?

  1. $n$ states (same as NFA)
  2. $n^2$ states
  3. $2^n$ states (exponential blow-up)
  4. $n!$ states
Show answer and solution

Correct answer: C. $2^n$ states (exponential blow-up)

1. The SUBSET (powerset) CONSTRUCTION converts an NFA to an equivalent DFA. 2. Each state of the DFA represents a SUBSET of the NFA's states (the set of NFA states the NFA could be in after reading the input). 3. The number of subsets of an $n$-element set is $2^n$. So the DFA has at most $2^n$ states. 4. For SOME languages, this exponential blow-up is unavoidable — there exist NFAs with $n$ states whose minimal equivalent DFA needs $2^n$ states. 5. For OTHER languages, the DFA may be much smaller (e.g. for a single-state NFA the DFA has 1 state). 6. Options A, B, D underestimate the bound. _Source: Jeff Erickson, "Models of Computation", §2.6 (Powerset construction)._

Open this question →

Which language is REGULAR (recognised by some DFA)?

  1. $\{a^n b^n \mid n \geq 0\}$ (equal numbers of a's then b's)
  2. $\{w \in \{0,1\}^* \mid w \text{ contains an even number of 1's}\}$
  3. $\{a^p \mid p \text{ is prime}\}$
  4. $\{ww \mid w \in \{0,1\}^*\}$ (palindrome-like duplications)
Show answer and solution

Correct answer: B. $\{w \in \{0,1\}^* \mid w \text{ contains an even number of 1's}\}$

1. Regular languages are exactly those recognised by some DFA / NFA / regular expression. 2. Option B (even number of 1's): a 2-state DFA suffices. State 0 = even count of 1's so far (accepting), state 1 = odd. Reading 0 stays put; reading 1 toggles. Regular ✓. 3. Option A ($a^n b^n$): NOT regular. Any DFA has finite states, but to remember how many a's were read (to check the matching number of b's) requires unbounded memory. Pumping lemma confirms. 4. Option C (primes): NOT regular. Primes are not a regular set. 5. Option D (duplications $ww$): NOT regular. Needs unbounded memory to remember the first half. 6. Useful rule of thumb: if a language requires COUNTING or MATCHING unbounded structures, it's NOT regular. _Source: Jeff Erickson, "Models of Computation", §2.5 + §2.10 (Regular vs non-regular examples)._

Open this question →

How to practise

  1. Choose a Theory of Computation question and try to work out your answer.
  2. Open the question to check the correct answer and read its worked solution.
  3. Continue in the app for bite-sized lessons, explanations and review with Quill. You can start without creating an account.

More Computer Science topics

AlgorithmsDatabase Management SystemsCompiler DesignOperating SystemsComputer NetworksDiscrete Mathematics