Convert the following regular expressions to NFAs using the procedure given in Theorem 1.54. In all parts, \(\Sigma=\\{\mathrm{a}, \mathrm{b}\\}\). a. \(\mathrm{a}(\mathrm{abb})^{*} \cup \mathrm{b}\) b. \(a^{+} \cup(a b)^{+}\) c. \(\left(\mathrm{a} \cup \mathrm{b}^{+}\right) \mathrm{a}^{+} \mathrm{b}^{+}\)

Let \(A\) be any language. Define \(D R O P-O U T(A)\) to be the language containing all strings that can be obtained by removing one symbol from a string in \(A\). Thus, DROP-OUT \((A)=\left\\{x z \mid x y z \in A\right.\) where \(\left.x, z \in \Sigma^{*}, y \in \Sigma\right\\} .\) Show that the class of regular languages is closed under the \(D R O P-O U T\) operation. Give both a proof by picture and a more formal proof by construction as in Theorem \(1.47\).

The formal description of a DFA \(M\) is $\left(\left\\{q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\\},\\{\mathrm{u}, \mathrm{d}\\}, \delta, q_{3},\left\\{q_{3}\right\\}\right)\(, where \)\delta$ is given by the following table. Give the state diagram of this machine. $$ \begin{array}{c|cc} & \mathrm{u} & \mathrm{d} \\ \hline q_{1} & q_{1} & q_{2} \\ q_{2} & q_{1} & q_{3} \\ q_{3} & q_{2} & q_{4} \\ q_{4} & q_{3} & q_{5} \\ q_{5} & q_{4} & q_{5} \end{array} $$

Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output \(w^{\mathcal{R}}\) for every input \(w\) if the input and output alphabets are \(\\{0,1\\}\).

If \(A\) is any language, let \(A_{\frac{1}{2}-}\) be the set of all first halves of strings in \(A\) so that \(A_{\frac{1}{2}-}=\\{x \mid\) for some \(y,|x|=|y|\) and \(x y \in A\\} .\) Show that if \(A\) is regular, then so is \(A_{\frac{1}{2}-}\).

Consider the language $F=\left\\{\mathrm{a}^{i} \mathrm{~b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0\right.\( and if \)i=1\( then \)\left.j=k\right\\} .$ a. Show that \(F\) is not regular. b. Show that \(F\) acts like a regular language in the pumping lemma. In other words, give a pumping length \(p\) and demonstrate that \(F\) satisfies the three conditions of the pumping lemma for this value of \(p\). c. Explain why parts (a) and (b) do not contradict the pumping lemma.