8 More Exercises

Exercise 8.1 (Homomorphisms vs the rest of operations) Given a homomorphism \sigma:\Sigma^*\to\Sigma^* and languages L,L_1,L_2\subseteq \Sigma^*, which of the following equalities are always true and which are in general false? (As usual, justify your answers)

\sigma(L_1L_2)=\sigma(L_1)\sigma(L_2).
For every n\in \mathbb N, \sigma(L^n)=\sigma(L)^n.
\sigma(L_1\cup L_2)= \sigma(L_1)\cup\sigma(L_2).
\sigma(L^*)=\sigma(L)^*.
\sigma(L^R)=\sigma(L)^R.
\sigma(\overline{L})=\overline{\sigma(L)}.
if \sigma(L)=L, then for every w\in L, \sigma(w)=w.

Exercise 8.2 Justify your answers to the following questions. All words and languages are taken over a fixed alphabet.

Does the cancellation law hold for concatenation of languages? That is, does AB=AC imply B=C for all languages A,B,C? What if we additionally impose that A\neq \emptyset, does it hold now?
Condition for a double equality. Given languages A,B,C,D such that A,B are non-empty, AB=CD, and all words in A and C have the same length, does it hold that A=C and B=D?

Exercise 8.3 (Characterizations) Justify your answers to the following questions. Languages are taken over a fixed alphabet.

When is a language equal to its Kleene star? Is L^2\subseteq L a necessary condition for the equality L= L^*? Is \lambda \in L a necessary condition for L= L^*? Which logic combination (\land, \lor, …) of the statements L^2\subseteq L and \lambda\in L constitutes a necessary and sufficient condition for the equality L= L^*?
When is a language included in its square? Is \lambda\in L a sufficient condition for the inclusion L\subseteq L^2? Is L = \emptyset a sufficent condition for L\subseteq L^2? Which logic combination (\land, \lor, …) of the statements L = \emptyset and \lambda\in L constitutes a sufficient and necessary condition for the inclusion L\subseteq L^2?
When does a language equal its square? Is L=L^* a sufficient condition for the equality L= L^2? Is L = \emptyset a sufficent condition for L= L^2? Which logic combination (\land, \lor, …) of the statements L = L^* and L=\emptyset constitutes a sufficient and necessary condition for the equality L= L^2?

Remember that if P and Q are two statements such that P implies Q, then P is said to be a sufficient condition for Q, while Q is said to be a necessary condition for P. In addition, P is called a characterization of Q when P is both a necessary condition and a sufficient condition for Q.

Exercise 8.4 (🔥) Prove that, for every alphabet \Sigma, there is a unique language L\subseteq \Sigma^* such that L=\overline{\Sigma L}. What is this language?

Hint

Give an alternative expression for L. Does L contain the empty word \lambda? If a word in L is of the form aw, with a\in \Sigma, is w in L or in \overline L? Once obtained the new expression, rewrite it as a function of L and resolve the recurrence relation.

8.1 Shifting a language

Given a language L, we define the shift of L, denoted \mathrm{S}(L), as the language that contains the words obtained by applying a circular shift to each word in L in all possible ways; formally,

\mathrm{S}(L) = \{vu:uv\in L\}\ .

Exercise 8.5 Argue whether the following statements are true (with a justification) or false (with a counterexample) for any L.

\mathrm{S}(L)^*= \mathrm{S}(L^*).
\overline{\mathrm{S}(L)}=\mathrm{S}(\overline{L}).
\mathrm{S}(L^R)=\mathrm{S}(L)^R.
\mathrm{S}(L_1\cup L_2) = \mathrm{S}(L_1)\cup \mathrm{S}(L_2).
\mathrm{S}(L_1\cap L_2) = \mathrm{S}(L_1)\cap \mathrm{S}(L_2).
\mathrm{S}(L_1L_2) = \mathrm{S}(L_1)\mathrm{S}(L_2).
\mathrm{S}(\sigma(L)) = \sigma(\mathrm{S}(L)), where \sigma is a homomorphism.

8.2 The Brzozowski derivative

The Brzozowski derivative is basically the opposite of concatenation. Given a language L\subseteq \Sigma^* and a word w\in \Sigma^*, the Brzozowski derivative of L w.r.t. w is \partial_{w}(L)=\{z:wz\in L\}\ .

Intuitively, \partial_{\textcolor{darkred}{\mathtt{s}}}(L) are all the words in L that start with \textcolor{darkred}{\mathtt{s}} but with \textcolor{darkred}{\mathtt{s}} removed. So \textcolor{darkred}{\mathtt{s}}\partial_{\textcolor{darkred}{\mathtt{s}}}(L) are all the words in L that start with \textcolor{darkred}{\mathtt{s}}.

Exercise 8.6 Show that for every w,z\in \Sigma^* and every language L\subseteq \Sigma^*, \partial_{wz}(L)=\partial_{w}(\partial_z(L))\ .

Thanks to the previous exercise it is enough to focus on the behavior of \partial_w(L) when w is a single symbol from \Sigma.

Exercise 8.7 Show that for every language L\subseteq \Sigma^*, L=\eta(L) \cup \bigcup_{\textcolor{darkred}{\mathtt{s}}\in \Sigma}\textcolor{darkred}{\mathtt{s}}\partial_{\textcolor{darkred}{\mathtt{s}}}(L)\ , where \eta(L)=\begin{cases}\{\varepsilon\}&\text{if }\varepsilon\in L\ ,\\ \emptyset &\text{otherwise}\ .\end{cases}

Exercise 8.8 Show the following properties of the Brzozowski derivative. For every \textcolor{darkred}{\mathtt{s}},\textcolor{darkred}{\mathtt{t}}\in \Sigma and languages L,L'\subseteq \Sigma^*

\partial_{\textcolor{darkred}{\mathtt{s}}}(\emptyset)=\emptyset.
\partial_{\textcolor{darkred}{\mathtt{s}}}(\{\varepsilon\})=\emptyset.
\partial_{\textcolor{darkred}{\mathtt{s}}}(\textcolor{darkred}{\mathtt{t}})=\begin{cases}\{\varepsilon\} & \text{if } \textcolor{darkred}{\mathtt{s}}=\textcolor{darkred}{\mathtt{t}}\ ,\\ \emptyset & \text{otherwise}\ .\end{cases}
\partial_{\textcolor{darkred}{\mathtt{s}}}(L\cup L')=\partial_{\textcolor{darkred}{\mathtt{s}}}(L)\cup \partial_{\textcolor{darkred}{\mathtt{s}}}(L').
\partial_{\textcolor{darkred}{\mathtt{s}}}(L^*)=\partial_{\textcolor{darkred}{\mathtt{s}}}(L)\cdot L^*.
\partial_{\textcolor{darkred}{\mathtt{s}}}(L\cdot L')=\partial_{\textcolor{darkred}{\mathtt{s}}}(L)\cdot L' \cup \eta(L)\cdot \partial_{\textcolor{darkred}{\mathtt{s}}}(L'), where \eta(L)=\begin{cases}\{\varepsilon\}&\text{if }\varepsilon\in L\ ,\\ \emptyset &\text{otherwise}\ .\end{cases}