The Exercises are taken out of Hopcroft, with their difficulty annotations preserved.

Exercise 4.2.1:

Suppose \(h\) is the homomorphism from the alphabet \(\{0,1,2\}\) to the alphabet \(\{a,b\}\) defined by \(h(0) = a\); \(h(1) = ab\), and \(h(2) = ba\).

a)

What is \(h(0120)\)?

b)

What is \(h(21120)\)?

c)

If \(L\) is the language \(L(\tb 0 \tb 1^*\tb 2)\), what is \(h(L)\)?

d)

If \(L\) is the language \(L(\tb 0 + \tb{12})\), what is \(h(L)\)?

e)

Suppose \(L\) is the language \(\{ababa\}\), that is, the language consisting of only the one string \(ababa\). What is \(h^{-1}(L)\)?

f)

If \(L\) is the language \(L(\tb a(\tb{ba})^*)\), what is \(h^{-1}(L)\)?

(not in text):

Let \(h\) be the homomorphism mapping strings in \(\{a,b,c\}^*\) to strings in \(\{0,1\}^*\) such that

\begin{eqnarray*} h(a) & = & 011, \\ h(b) & = & 0, \\ h(c) & = & 110. \end{eqnarray*}

a)

Find \(h^{-1}(L)\), where \(L = \{ 00110, 000111 \}\).

b)

Using the transformation described in class, give a regular expression for \(h(M)\), where \(M\) is the regular language denoted by \(a^*(bc + ca)^*\).

c)

Using the construction described in class, construct a DFA for \(h^{-1}(N)\), where \(N\) is recognized by the following DFA:

! Exercise 4.2.6: (optional)

Show that the regular languages are closed under the following operations:

a)

\(\textit{min}(L) = \{w\mid \mbox{$w$ is in $L$, but no proper prefix of $w$ is in $L$} \}\).

b)

\(\textit{max}(L) = \{w\mid \mbox{$w$ is in $L$ and for no string $x$ other than $\emptystr $ is $wx$ in $L$} \}\).

c)

\(\textit{init}(L) = \{ w\mid \mbox{for some string $x$, $wx$ is in $L$} \}\).

Hint: Like Exercise 4.2.2, it is easiest to start with a DFA for \(L\) and perform a construction to get the desired language.

*!! Exercise 4.2.8 (optional):

Let \(L\) be a language. Define \(\textit{half}(L)\) to be the set of first halves of strings in \(L\), that is, \(\{ w \mid \) for some \(x\) such that \(|x|=|w|\), we have \(wx\) in \(L\}\). For example, if \(L = \{\emptystr ,0010,011,010110\}\) then \(\textit{half}(L) = \{\emptystr ,00,010\}\). Notice that odd-length strings do not contribute to \(\textit{half}(L)\). Prove that if \(L\) is a regular language, so is \(\textit{half}(L)\).

!! (not in text; optional):

Let \(L\) be a language. Define \(\sqrt L\) to be the set \(\{ w\mid \mbox{$ww$ is in $L$} \}\). Prove that if \(L\) is regular, then so is \(\sqrt L\). Hint: Given a DFA for \(L\) with \(n\) many states, one can build a DFA for \(\sqrt L\) with \(n^n\) many states.

More generally, for \(k\ge 1\), define \(\sqrt [k]{L}\) to be the set \(\{ w \mid \mbox{$w^k$ is in $L$} \}\). Also define \(\sqrt [*]{L}\) to be the set \(\{ w \mid \mbox{$w$ is in $\sqrt [k]{L}$ for some $k\ge 1$} \}\). Similar constructions prove that if \(L\) is regular, then all these other languages are regular.

! Exercise 4.2.13:

We can use closure properties to help prove certain languages are not regular. Start with the fact that the language \[ L_{0n1n} = \{0^n1^n \mid n\ge 0\} \] is not regular. Prove the following languages not to be regular by transforming them, using operations known to preserve regularity, to \(L_{0n1n}\):

a)

\(\{0^i1^j \mid i\ne j\}\).

b)

\(\{0^n1^m2^{n-m} \mid n\ge m \ge 0\}\).

Exercise 4.2.14:

In Theorem 4.8, we described the “product construction” that took two DFAs and constructed one DFA whose languages is the intersection of the languages of the first two.

3.

Show how to modify the product construction so the resulting DFA recognizes the difference of the languages of the two given DFAs.

4.

Show how to modify the product construction so the resulting DFA recognizes the union of the languages of the two given DFAs.

(not in text):

Let \(L\) be a language. Define \(\textit{subseq}(L)\) to be the set of all strings obtained by removing zero or more symbols (anywhere) from a string in \(L\) and closing up the gaps. For example, if \(L = \{aabc,cab\}\), then \[ \textit{subseq}(L) = \{\emptystr ,a,b,c,aa,ab,ac,bc,aab,aac,abc,ca,cb,cab\}. \] Prove that if \(L\) is regular, then so is \(\textit{subseq}(L)\). (\(\textit{subseq}\) is short for “subsequence.” Actually, it is known that if \(L\) is any language whatsoever, then \(\textit{subseq}(L)\) is regular.) Hint: You can do this either by transforming regular expressions or by transforming \(\emptystr \)-NFAs.

! (not in the text; optional)

Let \(x\) and \(y\) be any two strings. A merge of \(x\) and \(y\) is any string obtained by merging the symbols of \(x\) with those of \(y\) in some arbitrary way, maintaining the order of the symbols from each string. More exactly, if \(|x|=m\) and \(|y|=n\), then a string \(z = z_1\cdots z_k\) is a merge of \(x\) and \(y\) if and only if

• \(k = m+n\),
• there exist \(1\le i_1<i_2<\cdots <i_m\le k\) such that \(x = z_{i_1}z_{i_2}\cdots z_{i_m}\),
• there exist \(1\le j_1<j_2<\cdots <j_n\le k\) such that \(y = z_{j_1}z_{j_2}\cdots z_{j_n}\), and
• \(\{i_1,\ldots ,i_m\} \cap \{j_1,\ldots ,j_n\} = \emptyset \).

For example, there are five different merges of the strings \(ab\) and \(bc\): \[ abbc \;\; abcb \;\; babc \;\; bacb \;\; bcab \]

Let \(A\) and \(B\) be any languages over the same input alphabet \(\Sigma \). Define \begin{align*} \merge{A}{B} \coloneqq \{ z\in \Sigma ^* \mid \mbox{$z$ is a merge of some $x\in A$ and some $y\in B$} \}. \end{align*}

Show that if \(A\) and \(B\) are regular, then so is \(\merge{A}{B}\). Hint: Given a DFA for \(A\) with \(r\) many states and an DFA for \(B\) with \(s\) many states, you can construct an NFA for \(\merge{A}{B}\) with \(rs\) many states.