Regular Expressions and Languages

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

• (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

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

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

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