From automata to expressions

1. We add $I_0 \xrightarrow{\varepsilon} P$ and $P \xrightarrow{\varepsilon} F$ (we call the new initial state $I_0$ so as not to confuse it with state I).
2. Remove I: predecessor P, successor P, loop $b$. Detour $(P, P)$: $b + ab^*a$, a loop on P. Remove P: predecessor $I_0$, successor $F$, loop $b + ab^*a$. Detour: $\varepsilon\,(b + ab^*a)^*\,\varepsilon$. The expression is $(b + ab^*a)^*$.
3. A word with an even number of $a$ can be cut into pieces: each $b$ read outside a pair of $a$ is a piece $b$; each pair of consecutive $a$ (in the order of the $a$ of the word), with the $b$ that separate them, is a piece $ab^*a$.

We normalise with $I \xrightarrow{\varepsilon} 0$ and $2 \xrightarrow{\varepsilon} F$.

1. Remove 1: predecessors 0 and 2 (by $a$), successor 2 (by $b$), loop $a$. $(0, 2)$: $aa^*b = a^+b$; $(2, 2)$: $a^+b$, a loop on 2. Remove 2: predecessor 0; successors 0 (by $b$) and $F$; loop $a^+b$. $(0, 0)$: $b + a^+b(a^+b)^*b$; $(0, F)$: $a^+b(a^+b)^*$. Remove 0: $(I, F)$:

2. Remove 2: predecessor 1 (by $b$); successors 1 (by $a$), 0 (by $b$), $F$. $(1, 1)$: $a + ba$; $(1, 0)$: $bb$; $(1, F)$: $b$. Remove 0: predecessors $I$ (by $\varepsilon$) and 1 (by $bb$); successor 1 (by $a$); loop $b$. $(I, 1)$: $b^*a$; $(1, 1)$: $a + ba + bbb^*a$. Remove 1: $(I, F)$:

3. Both denote the same language, but they do not look alike. In the second, $a + ba + bbb^*a = (\varepsilon + b + bbb^*)a = b^*a$. It becomes $b^*a(b^*a)^*b = (b^*a)^+b$, and since $(b^*a)^+$ denotes the words that end with $a$, this is $(a + b)^*ab$.

1. $X_P = bX_P + aX_I + \varepsilon$ (P is final) and $X_I = bX_I + aX_P$.
2. Arden on the second one, with $K = b$ and $L = aX_P$: $X_I = b^*aX_P$. We substitute: $X_P = bX_P + ab^*aX_P + \varepsilon = (b + ab^*a)X_P + \varepsilon$. Arden: $X_P = (b + ab^*a)^*$. It is the same result.
3. With $K = a + \varepsilon$, $X = K^*b = a^*b$ is a solution, but so is $X = (a + b)^*$: $(a + \varepsilon)(a + b)^* + b = (a + b)^*$, since $\varepsilon \cdot (a + b)^*$ already contains everything. Uniqueness is lost: when $\varepsilon \in K$, the equation “lets through” any word by prefixing it with $\varepsilon$.

1. Transitions: $0 \xrightarrow{0} 0$, $0 \xrightarrow{1} 1$, $1 \xrightarrow{0} 2$, $1 \xrightarrow{1} 0$, $2 \xrightarrow{0} 1$, $2 \xrightarrow{1} 2$. Remove 2: predecessor 1, successor 1, loop $1$: loop $01^*0$ on 1. Remove 1: predecessor 0, successor 0, loop $01^*0$: loop $1(01^*0)^*1$ on 0. With the loop $0$ already there, and 0 initial and final:

2. $11$: $1 \cdot 1$, with $(01^*0)^*$ empty, accepted. $110$: $11$ then $0$, accepted. $1001$: $1 \cdot (00) \cdot 1$, with $01^*0 = 00$, accepted. $101$: we would have to read $1$, then a piece of $(01^*0)^*$, then $1$; the middle would be $0$ alone, which is not of the form $01^*0$. Rejected, and $5$ is not a multiple of 3.