Theory of Computation

\(A \to a \mid aA\) generates \(a^{n}\) and \(B \to b \mid bB\) generates \(b^{n}\), for \(n \ge 1\).

So \(S \to aaB\) gives the strings \(a^{2}b^{n}\), and \(S \to Abb\) gives the strings \(a^{n}b^{2}\). Together, \(L(G) = \{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).

The other options do not match: for example, \(aabbb \in L(G)\), but it belongs to none of (B), (C) and (D).

Answer: A

The question asks for the FALSE statements.

• (A) True statement: a smaller NFA can exist. For example, if the given NFA (with \(n \ge 2\)) accepts every string, a 1-state NFA also accepts \(L\).
• (B) True statement: in the same example a 1-state DFA accepts \(L\), so a DFA with fewer than \(n\) states is possible.
• (C) True statement: the subset construction turns any \(n\)-state NFA into an equivalent DFA with at most \(2^{n}\) states.
• (D) False: by (C), some DFA for \(L\) has at most \(2^{n}\) states, so not every DFA can have more than \(2^{n}\).

Answer: D

Count the complement first: length-5 strings in which no two neighbouring symbols are the same. The first symbol has 3 choices and each of the next four has 2 (anything except the symbol just before it), so there are \(3 \times 2^{4} = 48\) such strings.

There are \(3^{5} = 243\) strings in all, so the number with at least one “aa”, “bb” or “cc” is \(243 - 48 = 195\).

Answer: 195

• \(L_2\): \(\alpha\) is a block of a's, so any \(a^k \beta a^k\) can be rewritten with \(\alpha = a\) by moving the extra a's into the middle part. So \(L_2 = {a(a+b)^+a}\), the strings of length at least 3 that start and end with \(a\), which is regular.
• \(L_1\): shrinking \(\alpha\) to one symbol fails, because \(\alpha\) may start and end with different symbols; for example \(abaab = (ab)(a)(ab) \in L_1\). A finite automaton would have to remember an arbitrarily long \(\alpha\).
• Pumping lemma proof for \(L_1\): \(w = a^n b\, a\, a^n b \in L_1\) (\(\alpha = a^n b\), \(\beta = a\)). Pumping up the leading a's gives \(a^{n+k} b\, a^{n+1} b\). Here \(\alpha\) must be a prefix ending in \(b\), i.e. \(a^{n+k} b\), and that is a suffix only when \(k = 1\), when nothing is left for \(\beta\). So the pumped string is not in \(L_1\), and \(L_1\) is not regular.

Answer: C

• \(L_2\) is context-free: \(a^m b^n c^{m+n} = a^m\,(b^n c^n)\,c^m\) is a nested pattern, generated by \(S \to aSc \mid aAc\), \(A \to bAc \mid bc\). A PDA pushes one symbol for every \(a\) and \(b\) and pops one for every \(c\).
• \(L_1\) is not context-free: it needs \(\#a = \#b\) and also \(\#c \gt \#a\) (because \(n \ge 1\)), so the same count \(m\) must be compared twice, but the single stack is used up matching the a's against the b's.
• Pumping lemma check: take \(a^p b^p c^{p+1}\). The pumped part (length \(\le p\)) cannot touch both a's and c's. If it contains a's or b's, pumping up gives \(\#a \ne \#b\) or \(\#a = \#b \ge p + 1 = \#c\); if it contains only c's, pumping down gives \(\#c \le p = \#a\). Either way the string leaves \(L_1\).

Answer: C

Label the states \(q_0\) (start), \(q_1\), \(q_2\), \(q_3\) (accepting) from left to right. \(q_0\) loops on \(a\) and goes to \(q_1\) on \(b\); \(q_1\) loops on \(b\) and goes to \(q_2\) on \(a\); \(q_2\) goes to \(q_3\) on \(b\) and back to \(q_0\) on \(a\); \(q_3\) goes to \(q_2\) on \(a\) and to \(q_1\) on \(b\).

So \(q_1\), \(q_2\) and \(q_3\) mean that the input read so far ends with \(b\), \(ba\) and \(bab\). The DFA accepts exactly the strings ending with \(bab\), so (C) is correct.

• (A) is wrong: \(bb\) has an even number of \(b\)'s but is rejected, while \(babab\) has three and is accepted.
• (B) is wrong: \(baba\) contains \(bab\) but ends in \(q_2\).
• (D) is wrong: \(b\) does not contain \(aba\) but is rejected.

Answer: C

Minimise by partition refinement. The output depends on the input (a Mealy machine), so first group the states by their output pair for \(X = 0\) and \(X = 1\).

• By outputs: {A, B, C, E} have (0, 0), {D, H} have (1, 0), {F} has (1, 1) and {G} has (0, 1).
• On \(X = 0\), A and C go to F but B and E go to D, and F, D are in different groups. So {A, B, C, E} splits into {A, C} and {B, E}. D and H have identical rows (G, A), so they stay together.
• Next pass: A goes to (F, B) and C to (F, E), with B and E now in one group; B, E and D, H still have identical rows. Nothing splits further.

The groups {A, C}, {B, E}, {D, H}, {F}, {G} give 5 states.

Answer: 5

A DFA is simply a DPDA that never touches its stack, so every regular language is accepted by some DPDA. That makes (A) true.

• (B) and (C) describe the same class, because non-deterministic PDAs accept exactly the context-free languages. Both fail because DPDAs are strictly weaker: the even-length palindromes \(\{ww^{R} \mid w \in \{a, b\}^{*}\}\) are context-free, but no DPDA can tell where the middle of the input is.
• (D) fails because a decidable language such as \(\{a^{n}b^{n}c^{n} \mid n \ge 0\}\) is not even context-free, so no pushdown automaton of either kind accepts it.

Answer: A

Emptiness of a CFG is decidable. Mark every variable that can derive a string of terminals: first those with a production whose body has only terminals (or is \(\varepsilon\)), then, repeatedly, any variable with a body made of terminals and marked variables. \(L(G_{1}) = \emptyset\) exactly when the start symbol is never marked, and the marking stops after at most as many rounds as there are variables. So (D) is decidable.

The other three are undecidable for CFGs:

• (A) equivalence of two CFGs;
• (B) whether two context-free languages share a string;
• (C) with \(R = \Sigma^{*}\), it asks whether \(G_{1}\) generates every string, which is undecidable.

Answer: D

Test each class against each property:

• Context-free languages are closed under union but not under intersection or complementation. For example, with \(m, n \ge 0\), \(\{a^{n}b^{n}c^{m}\}\) and \(\{a^{m}b^{n}c^{n}\}\) are context-free, but their intersection \(\{a^{n}b^{n}c^{n}\}\) is not. So (i) fits (a) and (b), not (c).
• Recursive languages are closed under union, intersection and complementation (swap a decider's accept and reject answers). So (ii) fits (a) and (c), not (b).
• Regular languages are closed under all three as well, so (iii) fits (a) and (c), not (b).

Option A fails on (ii) – (b) and option D on (iii) – (b), while every pair in B and C is true.

Answer: B, C