Closure properties

1. $((ab^*c + d)^*a)^t = a^t\,((ab^*c + d)^*)^t = a\,((ab^*c + d)^t)^* = a\,((ab^*c)^t + d)^* = a\,(c\,(b^*)^t\,a + d)^* = a(cb^*a + d)^*$.
2. Reversed transitions: $0 \xrightarrow{b} 0$, $1 \xrightarrow{a} 0$, $0 \xrightarrow{b} 1$, $2 \xrightarrow{a} 1$, $2 \xrightarrow{a, b} 2$; 2 becomes initial, 0 final. It is not deterministic: from 2, the letter $a$ leads to 2 and to 1; from 0, $b$ leads to 0 and to 1. It recognises the transpose of the language, that is… the words that contain $aa$: a word contains $aa$ if and only if its mirror image does.

1. The DFA is complete: we simply swap final and non-final states. 0 and 1 become final, 2 no longer is (it is now a sink).

2. We remove the sink 2 (useless), and normalise ($I \to 0$, $0 \to F$, $1 \to F$). Remove 1: predecessor 0 (by $a$), successors 0 (by $b$) and $F$. $(0, 0)$: $b + ab$; $(0, F)$: $\varepsilon + a$. Remove 0: $(b + ab)^*(\varepsilon + a)$. It is the expression of sheet 2.
3. After the swap, 0 and 1 are final. Since 0 is initial and loops on both letters, all words are accepted, $aa$ included. The swap gives the complement only on a deterministic and complete automaton; here the automaton is neither.

1.

Five accessible pairs, out of six possible: $(1, 1)$ is not accessible (we are in 1 in $L_1$ only after an $a$, and in 1 in $L_2$ only after a $b$).

2. Intersection: $(2, 1)$. Union (both DFAs are complete): the pairs in which one component is final, $(2, 0)$, $(2, 1)$, $(0, 1)$. Difference: $L_1$ final and $L_2$ non-final, $(2, 0)$.
3. A shortest path from $(0, 0)$ to $(2, 1)$: $a, a, b$. The word $aab$.

1. $(ab)^* \subseteq P$ (words of even length) if and only if $(ab)^* \cap \overline{P} = \emptyset$, where $\overline{P}$ is the set of words of odd length.
2. DFA of $(ab)^*$: $0 \xrightarrow{a} 1 \xrightarrow{b} 0$, 0 initial and final. DFA of $\overline{P}$: $E \xrightarrow{a,b} O \xrightarrow{a,b} E$, $E$ initial, $O$ final. Product from $(0, E)$: $(0, E) \xrightarrow{a} (1, O) \xrightarrow{b} (0, E)$. The only possible final pair, $(0, O)$, is not accessible: the intersection is empty, the inclusion holds.

1. The same automaton, with initial state $\delta(q_0, a)$.
2. It is $L \cap ((a + b)(a + b))^*$: the intersection of two regular languages. Or directly: the product of $A$ with the two-state automaton for the parity of the length.
3. We run two copies of $A$ at the same time on $u$: the first starts from $q_0$; the second starts from a state $p$ guessed at the start, which must be the one the first copy will reach. States: triples $(p, q, r)$, where $p$ is the guessed state (it never changes), $q$ the state of the first copy, $r$ that of the second. Initial states: the $(p, q_0, p)$ for every $p \in Q$. Transitions: $(p, q, r) \xrightarrow{a} (p, \delta(q, a), \delta(r, a))$. Final states: the $(p, p, r)$ with $r \in F$. At the end of $u$, the first copy is in $p$ (the middle of $uu$ was indeed $p$) and the second has read the second $u$ from $p$ and ends in $F$. It is an NFA (several initial states) with $|Q|^3$ states.