Encodings and homomorphisms of languages

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=10, C(b)=01, C(c)=\varepsilon$.

Construct a deterministic finite automaton that recognizes the language $C^{-1}(L)$ for the language $L=\left\{ w: w\text{ ends in 01 and contains an even number of ones }\right\}$.

A coding scheme from the alphabet $\Sigma =\left\{ a, b, c\right\}$ into the alphabet $\Omega =\left\{ 0,1,2\right\}$ is given by: $C=\left\{ (a a, 0),(a b c, 11),(b a, 21),(c, \varepsilon ),(b b, 2), (a b, 22),(b, 1)\right\}$. Find the sets of codes for the following words:

A coding scheme from the alphabet $\left\{ 0\right\}$ into the alphabet $\left\{ a, b\right\}$ is given by: $C=\left\{ (0, a),(00, b)\right\}$. Prove that the word $0^{n}$ can be encoded in $F_{n+1}$ ways, where $F_{i}$ is the corresponding Fibonacci number.

Let the language $L$ over the alphabet $\left\{ a, b\right\}$ consist of all words that begin with $a a$ and contain a number of symbols $a$ that is a multiple of three. The homomorphism $h:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b\right\}^{*}$ is given by the equalities $h(0)=a a a$, $h(1)=b a, h(2)=\varepsilon$. Determine which of the following three words belong to the preimage $h^{-1}(L)$ of the language $L$ under the homomorphism $h$:

Let the language $L$ over the alphabet $\left\{ a, b, c\right\}$ consist of all words that begin with $a a$ and contain the substring $b b$. Which of the following phrases defines the language $h(L)$, the image of $L$ under the following homomorphism $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}: h(a)=01, h(b)=11, h(c)=\varepsilon$?

Let the language $L$ over the alphabet $\left\{ a, b, c\right\}$ consist of all words that end with $b c c$ and contain the substring $a c a$. Which of the following phrases defines the language $h(L)$, the image of $L$ under the following homomorphism $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}: h(a)=0, h(b)=10, h(c)=\varepsilon$?

A coding scheme from the alphabet $\Sigma =\left\{ 0,1\right\}$ into the alphabet $\Omega =\left\{ a, b\right\}$ is given by: $C=\left\{ (00, a a),(01, b),(1, a)\right\}$. Find the results of encoding the following languages, represented by regular expressions:

A coding scheme from the alphabet $\Sigma =\left\{ 0,1\right\}$ into the alphabet $\Omega =\left\{ a, b\right\}$ is given by: $C=\left\{ (000, a b),(10, a),(11, b b)\right\}$. Find the results of encoding the following languages, represented by regular expressions:

Let a deterministic finite automaton $\mathfrak {M}=(\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \left\{ a, b, c\right\} , P, 0, \left\{ 2\right\} )$ be given, with program $P=\left\{ q_{0}, a \rightarrow q_{1} ; q_{0}, b \rightarrow q_{1} ; q_{0}, c \rightarrow q_{0} ; q_{1}, a \rightarrow q_{1} ; q_{1}, b \rightarrow q_{2} ; q_{1}, c \rightarrow q_{2} ; q_{2}, a \rightarrow q_{3} ; q_{2}, b \rightarrow q_{3} ; q_{2}, c \rightarrow q_{2} ; q_{3}, a \rightarrow q_{3} ; q_{3}, b \rightarrow q_{3} ; q_{3}, c \rightarrow q_{3}\right\}$, together with a homomorphism $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$, for which $h(a)=01, h(b)=11$, $h(c)=\varepsilon$. Which of the following three automata $\mathfrak {M}_{1}, \mathfrak {M}_{2}, \mathfrak {M}_{3}$ recognize the homomorphic image $h\left(L_{A}\right)$?

Given a deterministic finite automaton (Fig. 33) recognizing some language $L$. Construct a nondeterministic finite automaton recognizing the language $C(L)$ for the coding schemes $C$ from Problems

Let the homomorphism $C:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b\right\}^{*}$ be defined by the equalities $C(0)=a b, C(1)=b, C(2)=a a$.

Construct a deterministic finite automaton that recognizes the image $C(L)$ of the language

Let the homomorphism $C:\left\{ 0,1\right\}^{*} \rightarrow \left\{ a, b, c\right\}^{*}$ be defined by the equalities $C(0)=a a, C(1)=b c$.

Construct a deterministic finite automaton that recognizes the image $C(L)$ of the language

Let the homomorphism $C:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b, c\right\}^{*}$ be defined by the equalities $C(0)=b a, C(1)=\varepsilon , C(2)=b c$.

Construct a deterministic finite automaton that recognizes the language $C(L)$ for the language $L=\left\{ w:\text{ the digits 2 occur in }w\text{ in blocks of even length, and at least one such block is present}\right\}$

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=10, C(b)=01, C(c)=\varepsilon$.

Construct a deterministic finite automaton that recognizes the language $C^{-1}(L)$ for the language

and contains an even number of ones.

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=01, C(b)=11, C(c)=\varepsilon$.

Construct a deterministic finite automaton that recognizes the preimage $C^{-1}(L)$ of the language

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=00, C(b)=011, C(c)=01$.

Construct a deterministic finite automaton that recognizes the language $C^{-1}(L)$ for the language

Prove that any encoding operation $C$ for a language can be represented as a superposition of the preimage of a homomorphism $\psi$ and a homomorphism $\varphi : C(L)=\varphi \left(\psi^{-1}(L)\right)$ for some $\psi$ and $\varphi$.

Let us define the cylindrification operation, which is inverse to the projection operation. Let $C$ be the projection of the alphabet $\Sigma$ onto the alphabet $\Omega \subseteq \Sigma$. For any language $L \subseteq \Omega^{*}$ define its cylindrification to the alphabet $\Sigma$ as the language

Show that for an automatic language $L$ the language $Z_{\Sigma }(L)$ is also an automatic language. Propose a procedure for rebuilding an automaton recognizing $L$ into an automaton recognizing $Z_{\Sigma }(L)$.

Show that if the homomorphism $C: \Sigma^{*} \rightarrow \Omega^{*}$ is prefix-free, then the result of the inverse encoding $C^{-1}$ can be computed by a finite transducer. We assume $C^{-1}(w)$ may be anything if $w \notin \operatorname {rng} C$.

Let $C$ be a coding scheme from the alphabet $\Sigma$ into itself, and let $L$ be an automatic language over the alphabet $\Sigma$. Prove that the language $C^{*}(L)$ is also automatic:

Thus $C^{*}(L)$ contains the codes of words from $L$ that can be encoded, together with all words from $L$ that cannot be encoded.

Let $C$ be a coding scheme from the alphabet $\Sigma$ into itself. Give an example showing that the following language may fail to be automatic:

that is, $L$ is the set of words that, under encoding, can map to themselves. $\circledast$

Let $C: \Sigma^{*} \rightarrow \Omega^{*}$ be a language homomorphism. Prove that checking the correctness of $\varphi$ by means of a finite automaton (by analogy with Problems 523 and 524 on the preceding page) is possible if and only if one of the following two cases holds:

Find an unambiguous homomorphism $C: \Sigma^{*} \rightarrow \Omega^{*}$ that is computed by some finite transducer, but for which the inverse encoding $C^{-1}$ cannot be performed by any finite transducer. We assume $C^{-1}(w)$ may be anything if $w \notin \operatorname {rng} C$. $\circledast$