Theory of Computation

• (A) is the language of \(a^{*}b^{*}\), so it is regular.
• (B) Intersecting with \(\{a, b\}^{*}\) keeps only strings without \(c\), which forces \(m - n = 0\). What remains is \(\{a^{n}b^{n} \mid n \ge 0\}\), which is not regular.
• (C) A DFA only has to track \(\#_{a}(w) \bmod 7\) and \(\#_{b}(w) \bmod 9\): a product of two cyclic counters with \(7 \times 9 = 63\) states. Regular.
• (D) Requiring \(\#_{a}(w) = \#_{b}(w)\) needs an unbounded counter. If the language were regular, its intersection with \(a^{*}b^{*}\), namely \(\{a^{n}b^{n} \mid n \equiv 2 \pmod{7}\}\), would be regular too; the pumping lemma rules this out, because pumping inside the leading block of \(a\)'s changes the number of \(a\)'s but not of \(b\)'s.

Answer: A, C

A DFA only needs the product read so far as a residue mod 7, with residue 2 accepting. No symbol is a multiple of 7 and 7 is prime, so the product never becomes 0 and no dead state is needed. All six non-zero residues are reachable from the start state 1: 1, 2, 3, 4 directly, \(3 \times 4 \equiv 5\) and \(2 \times 3 = 6\).

The six states are pairwise distinguishable. For residues \(r \ne s\), take a string \(y\) with \(\mathit{prod}(y) \equiv 2r^{-1} \pmod{7}\) (one exists, since every non-zero residue is reachable). It takes \(r\) to 2 and accepts, but takes \(s\) to \(2sr^{-1} \not\equiv 2\) and rejects.

So the minimum DFA has 6 states.

Answer: 6

Regular languages are closed under complement, union and intersection.

• A: false. \(L_{1} \cap \overline{L_{2}} = \phi\) says only that no string of \(L_{1}\) lies outside \(L_{2}\), that is, \(L_{1} \subseteq L_{2}\). With \(L_{1} = \phi\) and \(L_{2} = \Sigma^{*}\) the condition holds but \(L_{1} \ne L_{2}\).
• B: false. If \(L_{1} = \Sigma^{*}\), then \(L_{1} \cup L_{3} = \Sigma^{*}\), which is regular.
• C: true. If \(\overline{L_{3}}\) were regular, its complement \(L_{3}\) would be regular too, which it is not.
• D: true. \(\overline{L_{1}}\) and \(\overline{L_{2}}\) are regular, and so is their union.

Answer: C, D

Each state records \(n_{0} - n_{1} \bmod 3\) for the input read so far: a 0 adds 1 and a 1 subtracts 1. State 1 is residue 0, states 2 and 5 are residue 1, and states 3 and 4 are residue 2; every arrow fits (for example, 3 goes to 2 on a 1, and 5 goes to 4 on a 0). So \(L(M)\) is the set of strings with \(n_{0}(w) - n_{1}(w) \equiv 0 \pmod{3}\).

• (A) is true: the input 1 takes state 2 to the accepting state 1 but takes state 4 to state 5.
• (B) and (C) are false: 3 and 4 have the same residue, as do 2 and 5, so every suffix leads both states of a pair to the same verdict. They are equivalent, not distinguishable.
• (D) is true: equal counts give a difference of 0.

Answer: B, C

In Chomsky Normal Form every rule has the form \(A \rightarrow BC\) or \(A \rightarrow a\), and \(|w| = 90\).

• Each \(A \rightarrow BC\) step adds one symbol to the sentential form. Growing from the single symbol \(S\) to 90 symbols takes exactly 89 such steps.
• Each \(A \rightarrow a\) step turns one variable into one terminal, and every one of the 90 terminals is produced this way: 90 steps.

The derivation therefore has \(89 + 90 = 179\) steps. In general a CNF derivation of a string of length \(n \ge 1\) takes \(2n - 1\) steps; the 10 variables do not affect the count.

Answer: 179

There are \(1 + 2 + 4 + 8 + 16 + 32 = 63\) binary strings of length 0 to 5, counting the empty string.

• \(r = 0^{*} + 1^{*}\): the empty string, plus the all-0 and the all-1 string of each length 1 to 5: \(1 + 5 \times 2 = 11\) strings.
• \(s = 01^{*} + 10^{*}\): one string \(01\cdots1\) and one string \(10\cdots0\) of each length 1 to 5: 10 strings.
• The strings 0 and 1 belong to both languages.

So \(11 + 10 - 2 = 19\) strings are in \(r\) or \(s\), and \(63 - 19 = 44\) are in neither. Forgetting to remove the two shared strings gives 42.

Answer: 44

Call the start state \(q_0\) and the accepting state \(q_1\). A 0 never changes the state and a 1 always switches it, so the DFA accepts exactly the strings with an odd number of 1s.

Option A follows the DFA directly. \(0^{*}1\) stays in \(q_0\) on 0s and moves to \(q_1\) on the first 1. From then on, every way of leaving \(q_1\) and coming back is either the self-loop 0 or a trip \(10^{*}1\) through \(q_0\), so \((0 + 10^{*}1)^{*}\) covers every continuation that ends in \(q_1\).

• B accepts the empty string, which has no 1s, and cannot produce 1.
• C cannot produce 111, which has three 1s.
• D forces a leading 0, so it misses 1, and it accepts 0.

Answer: A

Follow the two \(\epsilon\)-moves out of the start state 1.

• Into state 2, which accepts: the 0-loop through state 3 accepts \((00)^{*}\). From state 3, reached after an odd number of 0s, the \(\epsilon\)-move enters the accepting state 5, where the 1-loop adds any number of 11s: \(0(00)^{*}(11)^{*}\).
• Into state 4: one 1 reaches state 5, and each further 11 returns there: \(1(11)^{*}\).

So \(L(M) = (00)^{*} + 0(00)^{*}(11)^{*} + 1(11)^{*}\). Because \(0^{*} = (00)^{*} + 0(00)^{*}\) and \(0(00)^{*}\) is already inside \(0(00)^{*}(11)^{*}\), this is exactly option (B). Option (A) misses 0, (C) misses 0 and wrongly accepts 11, and (D) misses the empty string and 00011.

Answer: B

Follow the counts through a derivation, which starts with one \(S\). The rule \(S \rightarrow aSbS\) adds one \(a\), one \(b\) and one extra \(S\); \(S \rightarrow aS\) adds one \(a\); \(S \rightarrow c\) turns one \(S\) into \(c\). Every \(S\) must finally become a \(c\), so:

• \(n_c(w) = 1 + n_b(w)\), so (C) is true.
• Every \(b\) arrives with an \(a\), so \(n_a(w) \ge n_b(w) = n_c(w) - 1 \gt n_c(w) - 2\), and (B) is true.

The string \(w = c\) has \(n_a = n_b = 0\) and \(n_c = 1\). It breaks (A), since \(0 \gt 0\) is false, and (D), since \(1 \ne 0\).

Answer: B, C

The part \(b^{*}ab^{*}\) contributes exactly one \(a\), each repetition of \((ab^{*}ab^{*})\) adds two more, and \(b\)’s may appear anywhere. So \(L_1\) is the set of strings with an odd number of \(a\)’s.

Count such strings of length at most 4:

• length 0: none;
• length 1: just \(a\), 1 string;
• length 2: one \(a\), \(\binom{2}{1} = 2\) strings;
• length 3: one or three \(a\)’s, \(3 + 1 = 4\) strings;
• length 4: one or three \(a\)’s, \(4 + 4 = 8\) strings.

Total: \(1 + 2 + 4 + 8 = 15\). For each length \(n \ge 1\), exactly half of the \(2^{n}\) strings qualify.

Answer: 15