LEC TOC 5

Recall

Closure properties of recognizable languages: closed under boolean operations $(\cap ,\cup ,{-}^c)$. Saw the cartesian product construction for intersections.

Recognizable languages are also closed under homomorphisms, inverse homomorphisms, concatenation, and the kleene star.

Definition 1(Definition).

A homomorphism is a function $h:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ such that $h(uv)=h(u)h(v)$, and $h(ϵ)=ϵ$.

A homomorphism $h:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ is uniquely determined by its values on $\Sigma$.

[!Proposition]
If $L\subseteq {\Sigma }^{\ast }$ is a recognizable and $h:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ is a homomorphism, then $h(L)\subseteq {\Gamma }^{\ast }$ is also recognizable. If $M\subseteq {\Gamma }^{\ast }$ is recognizable, then $h^{-1}(M)\subseteq {\Sigma }^{\ast }$ is also recognizable.

[!Proof]-
Let $A$ be an NFA over $\Sigma$ recognizing $L$. Replace every edge in $A$ labelled $a\in \Sigma$ with a path which reads $h(a)\in {\Gamma }^{\ast }$.

Let $B$ be an NFA over $\Gamma$ recognizing $M$. Create a copy $B^{\prime }$ of $B$. Remove all transitions in $B^{\prime }$. Connect two states $\alpha ,\beta$ in $B^{\prime }$ with an arrow labelled $a\in \Sigma$ if $\beta$ can be reached from $\alpha$ on reading $h(a)$ in $B$.

[!Proposition]
Recognizable languages are closed under concatenation.

[!Proposition]
Recognizable languages are closed under iteration.

---

Rational languages

[!Definition]
The set of rational languages are the smallest class of languages such that

1. it contains every finite language
2. is closed under union
3. is closed under concatenation
4. is closed under Keene star