Question

A homomorphism is a function $\mathbf{f}\mathbf{:}\mathbf{\Sigma }\mathbf{-}\mathbf{\to }\mathbf{\Gamma }\mathbf{*}$from one alphabet to strings over another alphabet. We can extend f to operate on strings by defining:$\mathbf{f}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{=}\mathbf{f}\mathbf{\left(}{\mathbf{w}}_{\mathbf{1}}\mathbf{\right)}\mathbf{f}\mathbf{\left(}\mathbf{w}\mathbf{2}\mathbf{\right)}\mathbf{·}\mathbf{·}\mathbf{·}\mathbf{f}\mathbf{\left(}{\mathbf{w}}_{\mathbf{n}}\mathbf{\right)}\mathbf{,}\mathbf{where}\mathbf{}\mathbf{w}\mathbf{=}{\mathbf{w}}_{\mathbf{1}}{\mathbf{w}}_{\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathbf{w}}_{\mathbf{n}\mathbf{}}\mathbf{and}\mathbf{}\mathbf{each}\mathbf{}{\mathbf{w}}_{\mathbf{i}}\mathbf{\in }\mathbf{\Sigma }$.

We further extend $\mathbf{f}$to operate on languages by defining $\mathbf{f}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{f}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{\right|}\mathbf{w}\mathbf{\in }\mathbf{A}\mathbf{\}}\mathbf{,}$for any language $\mathbf{A}$.

a. Show, by giving a formal construction, that the class of regular languages is closed under homomorphism. In other words, given a DFA $\mathbf{M}$that recognizes $\mathbf{B}$and a homomorphism f, construct a finite automaton role="math" localid="1660800566802" ${\mathbf{M}}_{\mathbf{0}}$that recognizes $\mathbf{f}\mathbf{\left(}\mathbf{B}\mathbf{\right)}\mathbf{.}$Consider the machine role="math" localid="1660800575641" ${\mathbf{M}}_{\mathbf{0}}$that you constructed. Is it a DFA in every case?

b. Show, by giving an example, that the class of non-regular languages is not closed under homomorphism.

Short answer

a)The class of regular languages is closed under homomorphism.

b) The class of non-regular languages is not closed under homomorphism.

Step-by-step solution

Homomorphism.

A homomorphism is function $\mathrm{h}:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Delta }}^{*}$defined as follows:

• $\mathrm{h}(\in )=\in$and for $\mathrm{a}\in \mathrm{\Sigma },\mathrm{h}\left(\mathrm{a}\right)$is any string in ${\mathrm{\Delta }}^{*}$.

• For $\mathrm{a}={\mathrm{a}}_1{\mathrm{a}}_2...{\mathrm{a}}_{\mathrm{n}}\in \mathrm{\Sigma }*(\mathrm{n}\ge 2),\mathrm{h}\left(\mathrm{a}\right)=\mathrm{h}\left({\mathrm{a}}_1\right)\mathrm{h}\left({\mathrm{a}}_2\right)...\mathrm{h}\left({\mathrm{a}}_{\mathrm{n}}\right).$

• A homomorphism h maps a string$\mathrm{a}\in \mathrm{\Sigma }$ * to a string in${\mathrm{\Delta }}^{*}$ by mapping each character of a to a string $\mathrm{h}\left(\mathrm{a}\right)$∈${\mathrm{\Delta }}^{*}$.

• A homomorphism is a function from strings to strings that “respects” concatenation: for any$\mathrm{x},\mathrm{y}\in \mathrm{\Sigma }*,\mathrm{h}\left(\mathrm{xy}\right)=\mathrm{h}\left(\mathrm{x}\right)\mathrm{h}\left(\mathrm{y}\right).$ (Any such function is a homomorphism.)

The class of regular languages is closed under homomorphism

a).

Regular languages are closed under homomorphism, i.e., if $\mathrm{L}$is a regular language and $\mathrm{h}$is a homomorphism,

then$\mathrm{h}\left(\mathrm{L}\right)$is also regular.

Proof:

Use the representation of regular languages in terms of regular expressions to argue this.

• Define homomorphism as an operation on regular expressions

• Show that $\mathrm{L}\left(\mathrm{h}\left(\mathrm{R}\right)\right)=\mathrm{h}\left(\mathrm{L}\left(\mathrm{R}\right)\right)$

• Let $\left(\mathrm{R}\right)$be such that $\mathrm{L}=\mathrm{L}\left(\mathrm{R}\right).\mathrm{Let}\mathrm{R}0=\mathrm{h}\left(\mathrm{R}\right).\mathrm{Then}\mathrm{h}\left(\mathrm{L}\right)=\mathrm{L}\left(\mathrm{R}\right).$

•$\mathrm{h}(\in )=\in$ and$\mathrm{for}$$\mathrm{a}\in \mathrm{\Sigma },\mathrm{h}\left(\mathrm{a}\right)$ is any string in${\mathrm{\Delta }}^{*}$ .

• For $\mathrm{a}={\mathrm{a}}_1{\mathrm{a}}_2...{\mathrm{a}}_{\mathrm{n}}\in \mathrm{\Sigma }*(\mathrm{n}\ge 2),\mathrm{h}\left(\mathrm{a}\right)=\mathrm{h}\left({\mathrm{a}}_1\right)\mathrm{h}\left({\mathrm{a}}_2\right)...\mathrm{h}\left({\mathrm{a}}_{\mathrm{n}}\right).$

• A homomorphism h maps a string $\mathrm{a}\in \mathrm{\Sigma }$* to a string in${\mathrm{\Delta }}^{*}$ by mapping each character of a to a string $\mathrm{h}\left(\mathrm{a}\right)$∈${\mathrm{\Delta }}^{*}$.

• A homomorphism is a function from strings to strings that “respects” concatenation: for any $\mathrm{x},\mathrm{y}\in \mathrm{\Sigma }*,\mathrm{h}\left(\mathrm{xy}\right)=\mathrm{h}\left(\mathrm{x}\right)\mathrm{h}\left(\mathrm{y}\right).$(Any such function is a homomorphism.)

Hence, the class of regular languages is closed under homomorphism is proved.

The class of non-regular languages is not closed under homomorphism.

b).

• Show that $\mathrm{L}\left(\mathrm{h}\left(\mathrm{R}\right)\right)=\mathrm{h}\left(\mathrm{L}\left(\mathrm{R}\right)\right)$

• Let $\left(\mathrm{R}\right)$be such that $\mathrm{L}=\mathrm{L}\left(\mathrm{R}\right).\mathrm{Let}\mathrm{R}0=\mathrm{h}\left(\mathrm{R}\right).\mathrm{Then}\mathrm{h}\left(\mathrm{L}\right)=\mathrm{L}\left(\mathrm{R}\right).$

• $\mathrm{h}(\in )=\in$and for $\mathrm{a}\in \mathrm{\Sigma },\mathrm{h}\left(\mathrm{a}\right)$ is any string in ${\mathrm{\Delta }}^{*}$.

• For $\mathrm{a}={\mathrm{a}}_1{\mathrm{a}}_2...{\mathrm{a}}_{\mathrm{n}}\in \mathrm{\Sigma }*(\mathrm{n}\ge 2),\mathrm{h}\left(\mathrm{a}\right)=\mathrm{h}\left({\mathrm{a}}_1\right)\mathrm{h}\left({\mathrm{a}}_2\right)...\mathrm{h}\left({\mathrm{a}}_{\mathrm{n}}\right).$

• A homomorphism h maps a string $\mathrm{a}\in \mathrm{\Sigma }$* to a string in${\mathrm{\Delta }}^{*}$ by mapping each character of a to a string $\mathrm{h}\left(\mathrm{a}\right)$∈ ${\mathrm{\Delta }}^{*}$.

• A homomorphism is a function from strings to strings that “respects” concatenation: for any$\mathrm{x},\mathrm{y}\in \mathrm{\Sigma }*,\mathrm{h}\left(\mathrm{xy}\right)=\mathrm{h}\left(\mathrm{x}\right)\mathrm{h}\left(\mathrm{y}\right).$ (Any such function is a homomorphism.)

These properties does not follows by non-regular language so, it is not closed under homomorphism.

Hence, the class of non-regular languages is not closed under homomorphism.