List of top Theory of Computation Questions

The minimum number of states in a DFA accepting \( L = \{ w | w \text{ ends with } 01 \} \) over \( \Sigma = \{0, 1\} \) is _______ .
Which of the following is FALSE?
Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?
If the production rules are given as:
\( S \to XY | W \)
\( X \to aXb | \epsilon \)
\( Y \to cY | \epsilon \)
\( W \to aWc | bZ | \epsilon \)
\( Z \to bZ | \epsilon \)
Then the language generated by these rules is _______ .
The maximum number of transitions which can be performed over a state in a DFA? \( \Sigma = \{a, b, c\} \)
The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
Which of the following is a regular language?

Let \( \Sigma = \{1,2,3,4\} \). For \( x \in \Sigma^* \), let \( {prod}(x) \) be the product of symbols in \( x \) modulo 7. We take \( {prod}(\epsilon) = 1 \), where \( \epsilon \) is the null string. For example, \[ {prod}(124) = (1 \times 2 \times 4) \mod 7 = 1. \] Define \[ L = \{ x \in \Sigma^* \mid {prod}(x) = 2 \}. \] The number of states in a minimum state DFA for \( L \) is ___________. (Answer in integer)

Consider two grammars \( G_1 \) and \( G_2 \) with the production rules given below:

\[ G_1: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, \text{if } E \text{ then } S \text{ else } S \,|\, a \\ E &\to b \end{aligned} \] \[ G_2: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, M \\ M &\to \text{if } E \text{ then } M \text{ else } S \,|\, c \\ E &\to b \end{aligned} \] where if, then, else, a, b, c are the terminals.

Which of the following option(s) is/are CORRECT?
Given a Context-Free Grammar \( G \) as follows: \[ S \to A a \ |\ b A c \ |\ d c \ |\ b d a \] \[ A \to d \] Which ONE of the following statements is TRUE?
Let \( G_1, G_2 \) be Context-Free Grammars (CFGs) and \( R \) be a regular expression. For a grammar \( G \), let \( L(G) \) denote the language generated by \( G \). Which ONE among the following questions is decidable?

Consider the following deterministic finite automaton (DFA) defined over the alphabet, \( \Sigma = \{a, b\} \). Identify which of the following language(s) is/are accepted by the given DFA.


 

Consider the following two languages over the alphabet \( \{a, b, c\} \), where \( m \) and \( n \) are natural numbers. \[ L_1 = \{ a^m b^{m+n} c^{m+n} \mid m, n \geq 1 \} \] \[ L_2 = \{ a^m b^n c^{m+n} \mid m, n \geq 1 \} \] Which ONE of the following statements is CORRECT?
Consider the following two languages over the alphabet \( \{a, b\} \): \[ L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ { and } \beta \in \{a, b\}^+ \} \] \[ L_2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+ { and } \beta \in \{a, b\}^+ \} \] Which ONE of the following statements is CORRECT?
A regular language \(L\) is accepted by a non-deterministic finite automaton (NFA) with \(n\) states. Which of the following statement(s) is/are FALSE?
Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\[ S \to aaB \mid Abb \] \[ A \to a \mid AaA \] \[ B \to b \mid bB \] Which ONE of the languages \(L(G)\) is accepted by \(G\)?

Consider the following languages: 

\( L_1 = \{ ww \mid w \in \{a,b\}^* \} \) 
\( L_2 = \{ a^n b^n c^m \mid m, n \geq 0 \} \) 
\( L_3 = \{ a^m b^n c^n \mid m, n \geq 0 \} \) 

Which of the following statements is/are FALSE?

Consider the following languages: \[ L_1 = \{a^n w a^n | w \in \{a, b\}^*\} \] \[ L_2 = \{ w x w^R | w, x \in \{a, b\}^*, |w|, |x| > 0 \} \] Note that \( w^R \) is the reversal of the string \( w \). Which of the following is/are TRUE?

Which of the following is/are undecidable?
Which of the following statements is/are TRUE?

Which one of the following regular expressions correctly represents the language of the finite automaton given below? 
 

In a pushdown automaton \( P = (Q, \Sigma, \Gamma, \delta, q_0, F) \), a transition of the form 

where \( p, q \in Q \), \( a \in \Sigma \cup \{\epsilon\} \), and \( X, Y \in \Gamma \cup \{\epsilon\} \), represents \[ (q, Y) \in \delta(p, a, X). \] Consider the following pushdown automaton over the input alphabet \( \Sigma = \{a, b\} \) and stack alphabet \( \Gamma = \{\#, A\} \):

The number of strings of length 100 accepted by the above pushdown automaton is \(\underline{\hspace{2cm}}\).

Consider the following language: \[ L = \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} \] Which one of the following deterministic finite automata accepts \(L\)? 

For a Turing machine \(M\), \(\langle M \rangle\) denotes an encoding of \(M\). Consider the following two languages: \[ L_1 = \{\langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs}\} \] \[ L_2 = \{\langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on some input}\} \] Which one of the following options is correct?
Let \(\langle M \rangle\) denote an encoding of an automaton \(M\). Suppose that \(\Sigma = \{0,1\}\). Which of the following languages is/are NOT recursive?