All Theory of Computation questions

One or more correct

• AThe grammar is ambiguous
• BThe string $abb$ has two distinct derivations in this grammar
• CThe string $abab$ has only one rightmost derivation
• DThe language generated by the grammar is undecidable

One or more correct

• A32
• B65
• C1
• D128

One or more correct

• A$L_1$ is regular
• B$L_1 \cup L_2$ is regular
• C$\overline{L_2}$ is context-free
• D$L_1$ is context-free

One or more correct

• AThere is a string $s \in L(G)$ such that $n_1(s) < n_2(s)$
• BFor every string $s \in L(G)$, $n_1(s) \ge n_2(s)$
• CThere is a string $s \in L(G)$ such that $n_1(s) > 2n_2(s)$
• DFor every string $s \in L(G)$, $n_1(s) \le 2n_2(s)$

Single correct

• ATuring machine $M$ halts on all input strings in $\{0,1\}^*$
• BTuring machine $M$ accepts all input strings in $L$
• CTuring machine $M$ rejects all input strings in $\{0,1\}^* - L$
• DTuring machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^* - L$

One or more correct

• A$S \to aSb \mid \epsilon$
• B$E \to E + E \mid E * E \mid id$
• C$S \to aS \mid Sa \mid \epsilon$
• D$S \to aS \mid \epsilon$

One or more correct

• A$L(D_1) = L(D_2)$
• B$L(D_1)$ is a proper subset of $L(D_2)$
• C$L(D_1) \cap L(D_2) = \{\epsilon\}$
• D$(L(D_1) \cup L(D_2))^*$ consists of all strings in $\{0,1\}^*$ whose length is divisible by 3

One or more correct

• A$i + k = j + \ell$
• B$i = k$ and $j = \ell$
• C$i = \ell$ and $j = k$
• D$i + j = k + \ell$

Single correct

• A$L(G) = \{a^2 b^n \mid n \ge 1\} \cup \{a^n b^2 \mid n \ge 1\}$
• B$L(G) = \{a^n b^{2n} \mid n \ge 1\} \cup \{a^{2n} b^n \mid n \ge 1\}$
• C$L(G) = \{a^n b^n \mid n \ge 1\}$
• D$L(G) = \{a^{2n} b^{2n} \mid n \ge 1\}$

One or more correct

• A$L$ may have an accepting NFA with $< n$ states.
• B$L$ may have an accepting DFA with $< n$ states.
• CThere exists a DFA with $\le 2^n$ states that accepts $L$.
• DEvery DFA that accepts $L$ has $> 2^n$ states.

Single correct

• ABoth $L_1$ and $L_2$ are regular languages.
• B$L_1$ is a regular language but $L_2$ is not a regular language.
• C$L_1$ is not a regular language but $L_2$ is a regular language.
• DNeither $L_1$ nor $L_2$ is a regular language.

Single correct

• ABoth $L_1$ and $L_2$ are context-free languages.
• B$L_1$ is a context-free language but $L_2$ is not a context-free language.
• C$L_1$ is not a context-free language but $L_2$ is a context-free language.
• DNeither $L_1$ nor $L_2$ are context-free languages.

One or more correct

• AThe set of all strings containing an even number of $b$'s.
• BThe set of all strings containing the pattern $bab$.
• CThe set of all strings ending with the pattern $bab$.
• DThe set of all strings not containing the pattern $aba$.

Single correct

• AAny regular language.
• BAny context-free language.
• CAny language accepted by a non-deterministic pushdown automaton.
• DAny decidable language.

Single correct

• AIs $L(G_1) = L(G_2)$?
• BIs $L(G_1) \cap L(G_2) = \emptyset$?
• CIs $L(G_1) = L(R)$?
• DIs $L(G_1) = \emptyset$?

List I                          List II
(i)   Context free languages    (a) Closed under union
(ii)  Recursive languages       (b) Not closed under complementation
(iii) Regular languages         (c) Closed under intersection

One or more correct

• A(i) – (a), (ii) – (b), and (iii) – (c)
• B(i) – (b), (ii) – (a), and (iii) – (c)
• C(i) – (b), (ii) – (c), and (iii) – (a)
• D(i) – (a), (ii) – (c), and (iii) – (b)

One or more correct

• A$\{a^m b^n \mid m, n \ge 0\}$
• B$\{a, b\}^* \cap \{a^m b^n c^{m-n} \mid m \ge n \ge 0\}$
• C$\{w \mid w \in \{a, b\}^*,\ \#_a(w) \equiv 2 \pmod 7, \text{ and } \#_b(w) \equiv 3 \pmod 9\}$
• D$\{w \mid w \in \{a, b\}^*,\ \#_a(w) \equiv 2 \pmod 7, \text{ and } \#_a(w) = \#_b(w)\}$

Numerical answer

One or more correct

• A$L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \phi$
• B$L_1 \cup L_3$ is not regular
• C$\overline{L_3}$ is not regular
• D$\overline{L_1} \cup \overline{L_2}$ is regular

One or more correct

• AStates 2 and 4 are distinguishable in $M$
• BStates 3 and 4 are distinguishable in $M$
• CStates 2 and 5 are distinguishable in $M$
• DAny string $w$ with $n_0(w) = n_1(w)$ is in $L(M)$