List of top Computer Science and IT Engineering Questions on Theory of Computations asked in GATE CS

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet \(\{0, 1\}\), and has the set of states \(\{s, p, q, r\}\), with \(s\) being the start state and \(p\) being the only final state.

Which one of the following regular expressions correctly describes the language accepted by A?
 

Consider the context-free grammar \(G\) below: \[ S \;\to\; aSb \;|\; X \] \[ X \;\to\; aX \;|\; Xb \;|\; a \;|\; b \] where \(S\) and \(X\) are non-terminals, and \(a\) and \(b\) are terminal symbols. The starting non-terminal is \(S\). Which one of the following statements is CORRECT?
Consider the pushdown automaton (PDA) \(P\) over input alphabet \(\{a,b\}\) and stack alphabet \(\{\perp, A\}\) with start state \(s\) and acceptance by empty stack.
The transition sketch shows:
- In \(s\) on each \(a\) it pushes one \(A\) (i.e., \(a/\perp \to A\perp\) and \(a/A \to AA\)).
- On the first \(b\) it goes to \(p\) with \(b/A \to \epsilon\) and stays in \(p\) popping one \(A\) per \(b\) (\(b/A \to \epsilon\)).
- From \(p\) it may go to \(q\) by \(\epsilon/A \to \epsilon\), and in \(q\) it can keep popping \(A\)’s and finally pop \(\perp\) by \(\epsilon/\perp \to \epsilon\).
Question: Which option describes \(L(P)\)? IMAGE8
Consider the language \(L\) over the alphabet \(\{0,1\}\): \[ L = \{\, w \in \{0,1\}^* \;\mid\; \text{$w$ does not contain three or more consecutive $1$'s}\,\}. \] The minimum number of states in a Deterministic Finite-State Automaton (DFA) for \(L\) is ________.
Consider the language \(L\) over the alphabet \(\{0,1\}\): \[ L = \{\, w \in \{0,1\}^* \;\mid\; \text{$w$ does not contain three or more consecutive $1$'s}\,\}. \] The minimum number of states in a Deterministic Finite-State Automaton (DFA) for \(L\) is ________.