Finite automata

1. $\varepsilon$: yes (0 is initial and final). $abba$: we end in 2, no. $bbb$: we come back to 0, yes. $babab$: three $b$ (in positions 1, 3 and 5), we come back to 0, yes.
2. State $i$ remembers the number of $b$ read, modulo 3; the $a$ change nothing. The language: the words whose number of $b$ is a multiple of 3.
3. Deterministic: yes. Complete: yes, each state has one transition per letter. Trim: yes, each state is accessible and co-accessible.

1. Four states: 0 “no beginning of $aba$ in progress”, 1 “we have just read $a$”, 2 “we have just read $ab$”, 3 “$aba$ has been read” (final, loops on $a$ and $b$).

The trap is the transition $1 \xrightarrow{a} 1$: after $aa$, the second $a$ can start an $aba$. And $2 \xrightarrow{b} 0$: after $abb$, nothing is in progress any more.

2. Four states, one per pair of parities ($a$ even or odd, $b$ even or odd). Initial: (even, even). Final: (even, odd). Reading $a$ changes the first parity, reading $b$ the second. It is the product of two two-state automata (chapter 6).

3. If $u$ has value $n$, $u0$ has value $2n$ and $u1$ has value $2n + 1$. It is enough to remember $n$ modulo 3: three states 0, 1, 2, initial and final 0, and $r \xrightarrow{d} (2r + d) \bmod 3$.

For instance $110$ (six): $0 \xrightarrow{1} 1 \xrightarrow{1} 0 \xrightarrow{0} 0$, accepted.

1. Accessible: 0, 1, 2, 3 (4 has no incoming transition from 0). Co-accessible: 0, 1, 2, 4 (from 3, we never leave 3). Useful: 0, 1, 2.
2. $0 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{a} 1$, 2 final. It recognises $(ab)^+$: $ab$, $abab$, …
3. No: $0 \xrightarrow{b}$, $1 \xrightarrow{a}$, $2 \xrightarrow{b}$ are missing. We add a sink $p$, not final, with $0 \xrightarrow{b} p$, $1 \xrightarrow{a} p$, $2 \xrightarrow{b} p$ and $p \xrightarrow{a, b} p$. State 3 of the original automaton already played this role for $0 \xrightarrow{b}$.

1. The words that contain the factor $aba$ (the same as in the second exercise).
2. $abba$: $\{0\} \xrightarrow{a} \{0, 1\} \xrightarrow{b} \{0, 2\} \xrightarrow{b} \{0\} \xrightarrow{a} \{0, 1\}$. No final state: rejected.

$babab$: $\{0\} \xrightarrow{b} \{0\} \xrightarrow{a} \{0, 1\} \xrightarrow{b} \{0, 2\} \xrightarrow{a} \{0, 1, 3\} \xrightarrow{b} \{0, 2, 3\}$. Contains 3: accepted.

3. One path stays in 0 until the end. Others “guess” the beginning of an $aba$ at the second or at the fourth character. Guessing at the second: $0 \xrightarrow{b} 0 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{a} 3 \xrightarrow{b} 3$, successful. Guessing at the fourth: $\ldots \xrightarrow{a} 1 \xrightarrow{b} 2$, then the word is over, failure. There are also paths that do not read to the end (stuck). In total, three paths read the whole word, of which only one is successful: one is enough.

1. If the state is not initial, or not final, no path is successful: $\emptyset$. If it is initial and final, the paths are the loops; if $S \subseteq \Sigma$ is the set of letters that label a loop, the language is $S^*$. So: $\emptyset$, or $S^*$ for a subset $S$ of $\Sigma$ (with $S = \emptyset$, we get $\{\varepsilon\}$).
2. States $p$ (initial) and $q$. The letter $a$ leads from $p$ to $p$ or to $q$, and from $q$ to $p$ or to $q$. Depending on the cases and on the final states, we obtain in particular $\emptyset$, $a^*$, $\{\varepsilon\}$, $a^+$, $(aa)^*$, $a(aa)^*$. For instance $p \xrightarrow{a} q \xrightarrow{a} p$ with $p$ final gives the words of even length.