Minimisation and limits

1. $A \xrightarrow{a} B$, $A \xrightarrow{b} D$, $B \xrightarrow{a} E$, $B \xrightarrow{b} C$, $E \xrightarrow{b} F$: all six states are accessible.
2. Rank 0: $\{C, F\}$ and $\{A, B, D, E\}$. Rank 1: among the non-final states, $B$ and $E$ go into $\{C, F\}$ by $b$, $A$ and $D$ do not: $\{A, D\}$, $\{B, E\}$, $\{C, F\}$. Rank 2: $A$ and $D$ go into $\{B, E\}$ by $a$ and into $\{A, D\}$ by $b$; $B$ and $E$ go into $\{B, E\}$ by $a$ and $\{C, F\}$ by $b$; $C$ and $F$ go into $\{B, E\}$ by $a$ and $\{A, D\}$ by $b$. Nothing is split: three classes.
3. 

The words that end with $ab$: $AD$ “nothing useful”, $BE$ “we have just read $a$”, $CF$ “we have just read $ab$”.

1. $\varepsilon^{-1}L = ab^*$; $a^{-1}L = b^*$; $b^{-1}L = \emptyset$; $(ab)^{-1}L = b^*$; $(aa)^{-1}L = \emptyset$. Three distinct residuals: $ab^*$, $b^*$, $\emptyset$. Minimal automaton: three states $L$ (initial), $b^*$ (final), $\emptyset$ (sink), with $L \xrightarrow{a} b^*$, $L \xrightarrow{b} \emptyset$, $b^* \xrightarrow{b} b^*$, $b^* \xrightarrow{a} \emptyset$.
2. $a^*b^*$ (as long as only $a$ have been read), $b^*$ (after at least one $b$, with no $a$ afterwards), $\emptyset$ (after an $a$ that follows a $b$). Three states: $a^*b^*$ initial and final, $b^*$ final, sink.
3. The word $b^k$ is in $(a^k)^{-1}L$ (since $a^kb^k$ has as many $a$ as $b$), but not in $(a^{k'})^{-1}L$ for $k' \neq k$. There are infinitely many residuals: $L$ is not regular (Myhill–Nerode theorem).

1. Let $k$ be given; we choose $u = a^kb^k$. Since $|xy| \leq k$, $y = a^j$ with $j \geq 1$. Then $xy^2z = a^{k+j}b^k$ has more $a$ than $b$: it is not in the language. (Here, we must pump up: removing $y$ would give $a^{k-j}b^k$, which is in the language.)
2. Let $k$ be given; we choose $u = a^kba^k$, a palindrome. $y = a^j$ with $j \geq 1$, in the first block. $xz = a^{k-j}ba^k$ is not a palindrome.
3. Let $k$ be given; we choose $u = a^{k^2}$. $y = a^j$ with $1 \leq j \leq k$. Then $xy^2z = a^{k^2 + j}$, and $k^2 < k^2 + j \leq k^2 + k < (k+1)^2$: it is not a square.
4. If this language were regular, its intersection with $a^*b^*$ would be too (closure under intersection). But this intersection is $\{a^nb^n\}$, which is not regular.

1. False: $\{a^nb^n\} \subseteq \Sigma^*$, which is regular.
2. False: $L = \{a^nb^n\}$ and $\overline{L}$ are not regular (if $\overline{L}$ were, so would $L$ be, by complement), but $L \cup \overline{L} = \Sigma^*$ is.
3. False: with $L = \{ab\}$, the intersection is $\{ab\}$, finite hence regular. With $L = \emptyset$, it is empty.
4. True: it is a finite language (1001 words). The bound 1000 is enough: an automaton can count up to 1000, not arbitrarily far.
5. False: the lemma is only an implication. The course gives a counterexample, $\{a^ib^jc^j \mid i \geq 1\} \cup \{b^jc^k\}$.