15  More Exercises

Exercise 15.1 (🔥) Given w\in \Sigma^* and any regular language L\subseteq \Sigma^*, show that

  1. the language \mathtt{insert}(L,w)=\{xwy :x,y\in L\} is regular.
  2. the language \mathtt{delete}(L,w)=\{xy :xwy\in L\} is regular.

Exercise 15.2 (🔥) Given k\in \mathbb N, show that L_k=\{xy\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|x|_{\textcolor{darkred}{\mathtt{a}}}=k|y|_{\textcolor{darkred}{\mathtt{b}}}\} is regular if and only if k\in \{0,1\}.

The hard part is to show that for k>1, the language L_k is not regular. Think of k=2 first. The argument for a generic k is a simple generalization of this case.

Consider the reverse of L_2.