From expressions to automata

1. Three base symbols ($a$, $b$, $b$), one $+$, one star: $2 \times 5 = 10$ states.
2. 
3. Only one. The second $b$ must be the one of $8 \to 9$, so the first is read inside the star: $0 \to 1 \to 4 \xrightarrow{b} 5 \to 6 \to 7 \to 8 \xrightarrow{b} 9$, with six spontaneous transitions. The Thompson automaton has many partial paths (one can enter the $a$ branch, go back through 1…), but this does not give several successful paths for the same word.

1. $a^+b^*$: one or more $a$ (the transition $1 \to 0$ allows starting again), then some $b$.
2. $\mathrm{clo}^{-1}(0) = \{0, 1\}$, $\mathrm{clo}^{-1}(1) = \{1\}$, $\mathrm{clo}^{-1}(2) = \{1, 2\}$.
3. $0 \xrightarrow{a} 1$: 0 and 1 are in the backward closure of 0, we add $1 \xrightarrow{a} 1$. $2 \xrightarrow{b} 2$: we add $1 \xrightarrow{b} 2$. State 1 leads spontaneously to the final state 2: it becomes final.

Check: $\varepsilon$ rejected (0 is not final), $a$ accepted (in 1), $ab$ accepted (in 2), $b$ rejected (stuck in 0). As in the original automaton.

1. The words that end with $aa$ or with $bb$.

2.

3. Five states, out of the $2^4 = 16$ subsets: eleven are not accessible. Each state remembers the last letter read, and whether it repeats the previous one.

1. $\{0, 1, 2\}$ for 0, $\{1, 2\}$ for 1, $\{2\}$ for 2.
2. Start: $\{0, 1, 2\}$. By $a$: $\{0\}$, with closure $\{0, 1, 2\}$. By $b$: $\{1\}$, with closure $\{1, 2\}$. By $c$: $\{2\}$. From $\{1, 2\}$: $b$ leads to $\{1, 2\}$, $c$ to $\{2\}$, $a$ nowhere. From $\{2\}$: $c$ leads to $\{2\}$. The three subsets contain 2: they are all final.

1. $0 \xrightarrow{a, b} 0$, $0 \xrightarrow{a} 1$, $1 \xrightarrow{a, b} 2$, $2 \xrightarrow{a, b} 3$, 3 final.
2. $u$ and $v$ differ in at least one position $i \in \{1, 2, 3\}$; say $u_i = a$ and $v_i = b$. Take $w = a^{i-1}$, of length $i - 1$. In $uw$, the third letter from the end is $u_i = a$: $uw \in L_3$. In $vw$, it is $v_i = b$: $vw \notin L_3$.
3. In a DFA, if $u$ and $v$ led to the same state, so would $uw$ and $vw$, and they would both be accepted or both rejected. The 8 words of length 3 therefore lead to 8 different states.
4. Same reasoning: $L_k$ has an NFA with $k + 1$ states, and every DFA has at least $2^k$. Determinisation can cost an exponential, and it is not the algorithm's fault.