AS TOC 1

Problem 1

$$\begin{array}{rl}& \\ & c{c}^{\ast }a{c}^{\ast }a(a+c{)}^{\ast }+c^{\ast }a{c}^{\ast }a(a+c{)}^{\ast }b(a+c{)}^{\ast }+c^{\ast }a{c}^{\ast }b{c}^{\ast }a(a+c{)}^{\ast }+c^{\ast }b{c}^{\ast }a{c}^{\ast }a(a+c{)}^{\ast }\\ & +c^{\ast }a{c}^{\ast }a(a+c{)}^{\ast }b(a+c{)}^{\ast }b(a+c{)}^{\ast }+c^{\ast }a{c}^{\ast }b{c}^{\ast }a(a+c{)}^{\ast }b(a+c{)}^{\ast }+c^{\ast }a{c}^{\ast }b{c}^{\ast }b{c}^{\ast }a(a+c{)}^{\ast }\\ & +c^{\ast }b{c}^{\ast }a{c}^{\ast }b{c}^{\ast }a(a+c{)}^{\ast }+c^{\ast }b{c}^{\ast }b{c}^{\ast }a{c}^{\ast }a(a+c{)}^{\ast }+c^{\ast }b{c}^{\ast }a{c}^{\ast }a(a+c{)}^{\ast }b(a+c{)}^{\ast }\\ & +c^{\ast }b{c}^{\ast }b{c}^{\ast }b(b+c{)}^{\ast }+c^{\ast }a{c}^{\ast }b{c}^{\ast }b{c}^{\ast }b(b+c{)}^{\ast }+c^{\ast }b{c}^{\ast }a{c}^{\ast }b{c}^{\ast }b(b+c{)}^{\ast }+c^{\ast }b{c}^{\ast }b{c}^{\ast }a{c}^{\ast }b(b+c{)}^{\ast }\\ & +c^{\ast }b{c}^{\ast }b{c}^{\ast }b(b+c{)}^{\ast }a(b+c{)}^{\ast }\end{array}$$

---

Problem 2

Question

Let $\Sigma$ be a finite alphabet. Given a language $L$, define

$$\text{yolk}(L):=\{y:\exists z,x\in {\Sigma }^{\ast }\text{ such that }|x|=|y|=|z|\text{ and }xxyzz\in L\}.$$

Show that if $L$ is recognizable, $\text{yolk}(L)$ is recognizable.

Let $M=(Q,\Sigma ,\delta ,q_0,F)$ be a DFA recognizing $L$. For $a\in \Sigma$, let ${\sigma }_a:Q\to Q$ be the map $q\mapsto \delta (q,a)$. For $w=a_1\dots a_k\in {\Sigma }^{\ast }$ (where $a_1,\dots ,a_n\in \Sigma$), let ${\sigma }_w^{\prime }:Q\to Q$ be the map $q\mapsto ({\sigma }_{a_k}\circ \cdots \circ {\sigma }_{a_1})(q)$.

Define an automaton $\mathbf{M}=(\mathbf{Q},\Sigma ,\mathbf{\delta },{\mathbf{q}}_0,\mathbf{F})$ where

$$\begin{array}{rl}& \mathbf{Q}:=\{(S,\phi ):S\subseteq Q^Q,\phi \in Q^Q\},\\ & \mathbf{\delta }((S,\phi ),a):=(\{{\sigma }_b\circ \psi :\psi \in S,b\in \Sigma \},{\sigma }_a\circ \phi ),\\ & {\mathbf{q}}_0:=(\{{\sigma }_{ϵ}\},{\sigma }_{ϵ}),\\ & \mathbf{F}:=\{(S,\phi ):\exists (\alpha ,\beta \in S,q_f\in F)\text{ such that }(\alpha \circ \alpha \circ \phi \circ \beta \circ \beta )(q_0)=q_f\}.\end{array}$$

${\sigma }_{ϵ}$ denotes the identity on $Q$.

Claim 23.1(Claim).

$\mathbf{M}$ recognizes $\text{yolk(L)}$.

Proof.

et$y\in \text{yolk}(L)$. Then, $xxyzz\in L$ for some $x,z$ satisfying $|x|=|y|=|z|$. Let the state of $\mathbf{M}$ after having read $y$ be $(S,\phi )$. By construction, $S$ will contain ${\sigma }_x^{\prime }$ and ${\sigma }_z^{\prime }$, and $\phi$ will be ${\sigma }_y^{\prime }$. Then,

$$\begin{array}{rl}({\sigma }_z^{\prime }\circ {\sigma }_z^{\prime }\circ \phi \circ {\sigma }_x^{\prime }\circ {\sigma }_x^{\prime })(q)& ={\sigma }_{xxyzz}^{\prime }(q),\end{array}$$

and since $xxyzz\in L$, ${\sigma }_{xxyzz}^{\prime }(q)\in F$. Thus, $(S,\phi )\in \mathbf{F}$.

Conversely, let $\mathbf{M}$ be in an accept state $(S,\phi )$ after having read $y$. Then, there exist $\alpha ,\beta \in S$ and an accept state $q_f$ of $M$ such that $(\alpha \alpha \phi \beta \beta )(q_0)=q_f$. By construction, $\alpha$ and $\beta$ are of the form ${\sigma }_z^{\prime }$ and ${\sigma }_x^{\prime }$ respectively such that $|x|=|y|=|z|$, and $\phi ={\sigma }_y^{\prime }$. Thus, we have ${\sigma }_{xxyzz}^{\prime }(q_0)=q_f$, which implies $M$ accepts $xxyzz$.□

---

Problem 3

Let $M=(Q,\Sigma ,\delta ,q_0,F)$ be a DFA recognizing $L$. Define ${\mathbf{M}}_{\text{max}}=(Q,\Sigma ,\delta ,q_0,{\mathbf{F}}_{\text{max}})$ by

$${\mathbf{F}}_{\text{max}}:=\{q:q\in F,\text{ and }\nexists w\in {\Sigma }^{\ast }\text{ such that }{\sigma }_w^{\prime }(q)\in F\}.$$

Claim 23.2(Claim).

${\mathbf{M}}_{\text{max}}$ recognizes $\text{max(L)}$.

Proof.

et$y\in \text{max(L)}$. Then, there does not exist $w\in L$ such that $w>y$. This is precisely when ${\sigma }_y^{\prime }(q_0)\in {\mathbf{F}}_{\text{max}}$. Similarly, if ${\mathbf{M}}_{\text{max}}$ accepts $y$, by the construction of ${\mathbf{F}}_{\text{max}}$ there does not exist $w>y$ such that $M$ accepts $w$.□

Define an NFA ${\mathbf{M}}_{\text{min}}=(Q,\Sigma ,{\mathbf{\delta }}_{\text{min}},q_0,F)$ by

$${\mathbf{\delta }}_{\text{min}}(q,a)=\{\begin{array}{ll}\{\delta (q,a)\}& q\notin F\\ \varnothing & q\in F.\end{array}$$

Claim 23.3(Claim).

${\mathbf{M}}_{\text{min}}$ recognizes $\text{min}(L)$.

Proof.

et$y\in \text{min(L)}$. Then, there does not exist $w<y$ such that $M$ accepts $w$, and by the construction of ${\mathbf{\delta }}_{\text{min}}$, ${\mathbf{M}}_{\text{min}}$ must accept $y$. Conversely, if ${\mathbf{M}}_{\text{min}}$ accepts $y$, then ${\mathbf{M}}_{\text{min}}$ cannot have occupied any final state while reading $y$, hence $y\in \text{min(L)}$.□