GATE CSE Theory of Computation — practice questions
28 free MCQs with worked solutions. Tap any question for the answer + explanation, or practice them all in the app.
Practice GATE CSE Theory of Computation in the app →A DETERMINISTIC FINITE AUTOMATON (DFA) is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$. Which component represeA DFA accepts an input string $w$ if and only ifWhich is a key difference between a DFA and an NFA (Non-deterministic Finite Automaton)?An NFA with $n$ states can be converted to an equivalent DFA. The resulting DFA has AT MOST how many states?Which language is REGULAR (recognised by some DFA)?The REGULAR EXPRESSION $(0 + 1)^* 0$ describes the language of all strings over $\{0, 1\}$Regular languages are CLOSED under which operations?The PUMPING LEMMA for regular languages states that for any regular language $L$, there exists a pumping lengtThe Kleene STAR $L^*$ of a language $L$ is defined asAn $\varepsilon$-TRANSITION in an NFA allows the automaton toWhich of the following is a CORRECT regular expression for the language $L = \{w \in \{0,1\}^* \mid w \text{ cIf $L$ is regular and $L'$ is its complement (over the same alphabet), thenConsider the language $L = \{0^i 1^j \mid i + j \text{ is even}\}$. Is this language regular?Which of these is an example of an IRREGULAR (non-regular) language?A CONTEXT-FREE GRAMMAR (CFG) is a 4-tuple $G = (V, \Sigma, R, S)$. What does $R$ represent?Consider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated isA CFG is AMBIGUOUS ifContext-free languages are RECOGNISED by which type of machine?Chomsky Normal Form (CNF) restricts CFG production rules to which shapes?Is the language $L = \{a^n b^n c^n \mid n \geq 0\}$ context-free?Context-free languages are CLOSED under which of the following operations?A LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. Why is left recursionThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isEvery regular language is also context-free. The PROOF construction isConsider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isWhich of the following languages is CONTEXT-FREE?What is a LEFTMOST DERIVATION?Which class of grammars generates ALL recursively enumerable languages?