Chapter 1

- 1.1 The following are the state diagrams of two DFAs, \(M_{1}\) and \(M_{2}\). Answer the following questions about each of these machines. Solution: \alreadyanswered
- 1.2 Give the formal description of the machines \(M_{1}\) and \(M_{2}\) pictured in Exercise 1.1. Solution: \alreadyanswered
- 1.3 The formal description of a DFA \(M\) is \((\{q_{1},q_{2},q_{3},q_{4},q_{5}\},\{u,d\},\delta,q_{3},\{q_{3}\})\), where \(\delta\) is given by the following table. Give the state diagram of this machine. \(u\) \(d\) \(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}\) Solution: {tikzpicture}[shorten ¿=1pt,node distance=2cm,initial text=,on grid,auto] \node[state] (q_1) \(q_{1}\); \node[state] (q_2) [right=of q_1] \(q_{2}\); \node[state,initial above,accepting](q_3) [right=of q_2] \(q_{3}\); \node[state] (q_4) [right=of q_3] \(q_{4}\); \node[state] (q_5) [right=of q_4] \(q_{5}\); ->]Ω(q_1)␣edgeloop above] node \(u\) (q_1) edge [bend left=20] node \(d\) (q_2) (q_2) edge [bend left=20] node \(u\) (q_1) edge [bend left=20] node \(d\) (q_3) (q_3) edge [bend left=20] node \(u\) (q_2) edge [bend left=20] node \(d\) (q_4) (q_4) edge [bend left=20] node \(u\) (q_3) edge [bend left=20] node \(d\) (q_5) (q_5) edge [bend left=20] node \(u\) (q_4) edge [loop above] node \(d\) (q_5);
- 1.4
Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts, \(\Sigma=\{a,b\}\).
Note: for simplicity, I omit the state diagrams.
- a.
Solution: The state set is \(Q=\{q_{i,j}\colon 0\leq i\leq 3,0\leq j\leq 2\}\), with transition function:
- * \(\delta(q_{i,j},a)=q_{i+1,j}\) for all \(0\leq i\leq 2,0\leq j\leq 2\),
- * \(\delta(q_{i,j},b)=q_{i,j+1}\) for all \(0\leq i\leq 3,0\leq j\leq 1\).

- b. Solution: \alreadyanswered
- c.
Solution: the state set is \(Q=\{q_{i,j}\colon i\in\{0,1,2,3\},j\in\{even,odd\}\}\), with transition function:
- * \(\delta(q_{i,even},a)=q_{i,odd}\) for all \(i\),
- * \(\delta(q_{i,odd},a)=q_{i,even}\) for all \(i\),
- * \(\delta(q_{i,j},b)=q_{i+1,j}\) for \(i\in\{0,1,2\},j\in\{even,odd\}\),
- * \(\delta(q_{3,j},b)=q_{3,j}\) for \(j\in\{even,odd\}\).

- d. Solution: \alreadyanswered
- e. Solution: the state set is \(Q=\{ij\colon i,j\in\{0,1,2\}\}\), with transition function in \Creflbl:1.4e. \label{lbl:1.4e}1.4e state table. State \(\downarrow\) Symbol \(\rightarrow\) \(a\) \(b\) 00 (start) 10 21 01 11 22 02 12 22 10 (final) 10 11 11 (final) 11 12 12 12 12 20 20 21 21 21 22 22 22 22
- f. Solution: the state set is \(Q=\{ij\colon i,j\in\{0,1\}\}\), with transition function in \Creflbl:1.4f. \label{lbl:1.4f}1.4f state table. State \(\downarrow\) Symbol \(\rightarrow\) \(a\) \(b\) 00 (start) 01 10 01 00 11 10 01 00 11 (final) 00 01
- g. Solution: the state set is \(Q=\{ij\colon i,j\in\{0,1\}\}\), with transition function in \Creflbl:1.4g. \label{lbl:1.4g}1.4g state table. State \(\downarrow\) Symbol \(\rightarrow\) \(a\) \(b\) 00 (start) 11 10 01 (final) 10 11 10 01 00 11 00 01

- a.
Solution: The state set is \(Q=\{q_{i,j}\colon 0\leq i\leq 3,0\leq j\leq 2\}\), with transition function:
- 1.5
Each of the following languages is the complement of a simpler languages. In each part, construct DFAs for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, \(\Sigma=\{a,b\}\).
Note: for simplicity, I omit the state diagrams.
- a. Solution: \alreadyanswered
- b. Solution: \alreadyanswered

- 1.6
Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0, 1}.
- a. Solution: \alreadyanswered
- f. Solution: \alreadyanswered

- 1.7
Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, \(\Sigma=\{a,b\}\).
- a. Solution: \alreadyanswered
- b. Solution: \alreadyanswered

- 1.11 Prove that every NFA can be converted to an equivalent one that has a single accept state. Solution: \alreadyanswered
- 1.20
For each of the following languages, give two strings that are members and two strings that are not members–a total of four strings for each part. Assume the alphabet \(\Sigma=\{a,b\}\) in all parts.
- a. Solution: 2 members: \(ab,aa\); 2 not members: \(ba,bab\).
- b. Solution: 2 members: \(ab,abab\); 2 not members: \(b,ba\).
- c. Solution: 2 members: \(aa,bb\); 2 not members: \(ba,ab\).
- d. Solution: 2 members: \(\epsilon,aaa\); 2 not members: \(b,bb\).
- e. Solution: 2 members: \(aba,aaba\); 2 not members: \(b,bb\).
- f. Solution: 2 members: \(aba,bab\); 2 not members: \(a,b\).
- g. Solution: 2 members: \(b,ab\); 2 not members: \(ba,bb\).
- h. Solution: 2 members: \(a,ba\); 2 not members: \(ab,b\).

- 1.23 Let \(B\) be any language over the alphabet \(\Sigma\). Prove that \(B=B^{+}\) iff \(BB\subseteq B\). Solution: \alreadyanswered
- 1.29
Use the pumping lemma to show that the following languages are not regular.
- a. Solution: \alreadyanswered
- b. Solution: \(A_{2}\) = {\(www\) \(|\) \(w\in\{a,b\}^{*}\)}. Suppose that \(A_{2}\) were regular, and let \(p\) be the constant for \(A_{2}\) as given by the pumping lemma. Then, let \(s=a^{p}ba^{p}ba^{p}b\in A_{2}\). Therefore, we can decompose \(s\) as \(xyz\), where \(|xy|\leq p,|y|>0\), and \(xy^{i}z\in A_{2}\) for \(\forall i\in\mathbb{N}\). Since \(|xy|\leq p\), \(x,y\) consist entirely of \(a\)’s; therefore, we can write \(x=a^{c}\), \(y=a^{d}\), and \(z=a^{p-c-d}ba^{p}ba^{p}b\), where \(c\geq 0,d>0,p-c-d\geq 0\). For the third condition, choose \(i=2\): \(w=xy^{2}z=a^{c}a^{2d}a^{p-c-d}ba^{p}ba^{p}b=a^{p+d}ba^{p}ba^{p}b\). Since \(d>0\), \(w\notin A_{2}\): therefore, we have a contradiction, and \(A_{2}\) is not regular.
- c. Solution: \alreadyanswered

- 1.31
For any string \(w=w_{1}w_{2}\cdots w_{n}\), the
*reverse*of \(w\), written \(w^{\mathcal{R}}\), is the string \(w\) in reverse order, \(w_{n}\cdots w_{2}w_{1}\). For any language \(A\), let \(A^{\mathcal{R}}=\{w^{\mathcal{R}}|w\in A\}\). Show that if \(A\) is regular, so is \(A^{\mathcal{R}}\). Solution: For any regular language \(A\), let \(M=(Q,\Sigma,\delta,q_{0},F)\) be the DFA recognizing \(A\). We need to construct an NFA/DFA \(N\) such that \(L(N)=A^{\mathcal{R}}\). Let \(N=(Q^{\prime},\Sigma,\delta^{\prime},q_{0}^{\prime},\{q_{0}\})\), where \(q_{0}^{\prime}\notin Q\) and \(Q^{\prime}=Q\cup\{q_{0}^{\prime}\}\). Define \(\delta^{\prime}\) as: \(\delta^{\prime}(q_{0}^{\prime},\epsilon)=F\), and \(\delta^{\prime}(q_{0}^{\prime},a)=\emptyset,\forall a\in\Sigma\). Also, \(\forall(q,a)\in Q\times\Sigma,\delta^{\prime}(q,a)=\{q^{\prime}|\delta(q^{\prime},a)=q\}\). Another way to approach this problem is an informal explanation: we reverse all of the transitions of \(M\), and set the accept state of \(N\) to be \(M\)’s start state. Also, introduce a new state \(q_{0}^{\prime}\) as \(N\)’s start state, which goes to every accept state in \(M\) by an \(\epsilon\)-transition. - 1.39 The construction in Theorem 1.54 shows that every GNFA is equivalent to a GNFA with only two states. We can show that an opposite phenomenon occurs for DFAs. Prove that for every \(k>1\), a language \(A_{k}\subseteq\{0,1\}^{*}\) exists that is recognized by a DFA with \(k\) states but not by one with only \(k-1\) states. Solution: let \(L_{k}=\{0^{i}\;|\;i\geq k-1\}\). This language consists of strings of length \(\geq k-1\). Therefore, no DFA of \(k-1\) states can recognize this language, but certainly one of \(k\) states can.
- 1.40
Recall that string \(x\) is a prefix of string \(y\) if a string \(z\) exists where \(xz=y\), and that \(x\) is a proper prefix of \(y\) if in addition \(x\neq y\). In each of the following parts, we define an operation on a language \(A\). Show that the class of regular languages is closed under that operation.
- a. Solution: \alreadyanswered

- 1.42
For languages \(A\) and \(B\), let the
*shuffle*of \(A\) and \(B\) be the language {\(w\) \(|\) \(w=a_{1}b_{1}...a_{k}b_{k}\), where \(a_{1}...a_{k}\in A\) and \(b_{1}...b_{k}\in B\), each \(a_{i},b_{i}\in\Sigma^{*}\)}. Show that the class of regular languages is closed under shuffle. Solution: Let \(D_{A}=(Q_{A},\Sigma,\delta_{A},q_{A},F_{A}\) and \(D_{B}=(Q_{B},\Sigma,\delta_{B},q_{B},F_{B}\) be the DFAs recognize \(A\) and \(B\), respectively. We will design a DFA \(D=(Q,\Sigma,\delta,q_{0},F)\) such that it recognizes the shuffle of \(A\) and \(B\) as follows:- – \(Q=Q_{A}\times Q_{B}\times\{A,B\}\).
- – \(q_{0}=(q_{A},q_{B},A)\).
- – \(F=F_{A}\times F_{B}\times\{A\}\).
- –
For \(\delta\):
- * \(\delta((x,y,A),a)=(\delta_{A}(x,a),y,B)\).
- * \(\delta((x,y,B),b)=(x,\delta_{B}(y,b),A)\).

- 1.44 Let \(B\) and \(C\) be languages over \(\Sigma=\{0,1\}\). Define \(B\xleftarrow{1}C\) = {\(w\in B|\) for some \(y\in C\), strings \(w\) and \(y\) contain equal numbers of 1s}. Show that the class of regular languages is closed under the \(\xleftarrow{1}\) operation. Solution: \alreadyanswered
- 1.45 Let \(A/B=\{w|wx\in A\) for some \(x\in B\)}. Show that if \(A\) is regular and \(B\) is any language, then \(A/B\) is regular. Solution: Let \(M=(Q,\Sigma,\delta,q_{0},F)\) be a DFA such that \(L(M)=A\), and \(\Sigma\) is the union of the alphabets of \(A\) and \(B\). Let \(F_{r}=\{q\in Q|\exists x\in B\) such that \(M\) can reach a final state when having read \(x\), starting at \(q\)}. Therefore, \(L(M)=A/B\).
- 1.48 Let \(\Sigma=\{0,1\}\) and let \(D=\{w|w\) contains an equal number of occurrences of the substrings 01 and 10}. Thus 101 \(\in D\) because 101 contains a single 01 and a single 10, but 1010 \(\notin D\) because 1010 contains two 10s and one 01. Show that \(D\) is a regular language. Solution: \(D\) is just precisely described by the regular expression \((1^{+}0^{*}1^{+})^{*}\cup(0^{+}1^{*}0^{+})^{*}\)
- 1.50 Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output \(w^{R}\) for every input \(w\) if the input and output alphabets are {0, 1}. Solution: \alreadyanswered
- 1.52
Myhill-Nerode theorem. Refer to Problem 1.51. Let \(L\) be a language and let \(X\) be a set of strings. Say that \(X\) is
*pairwise distinguishable by L*if every two distinct strings in \(X\) are distinguishable by \(L\). Define the*index of L*to be the maximum number of elements in any set that is pairwise distinguishable by \(L\). The index of \(L\) may be finite or infinite. Solution: \alreadyanswered - 1.53 Let \(\Sigma\) = {0, 1, +, =} and \(ADD\) = { \(x=y+z\) \(|\) \(x,y,z\) are binary integers, and \(x\) is the sum of \(y\) and \(z\)}. Show that \(ADD\) is not regular. Solution: Assume that \(ADD\) is regular. Therefore, there exists a pumping length \(p\in\mathbb{Z}\) such that the three conditions of the Pumping Lemma are satisfied. Choose \(w\) as \(1^{p}=0^{p}+1^{p}\). Clearly, \(w\in ADD\). By the conditions of the Pumping Lemma, we can partition \(w=xyz\) such that \(|xy|\leq p,|y|>0\), and \(xy^{i}z\in ADD\) for \(\forall i\in\mathbb{N}\). By the first and second conditions of the Pumping Lemma, \(x\) and \(y\) consist entirely of 1s, i.e. \(x=1^{a},y=1^{b},z=1^{p-a-b}=0^{p}+1^{p}\) for \(a\geq 0,b>0\). By the third condition, \(xy^{i}z\in ADD\) for \(\forall i\in\mathbb{N}\). Choose \(i=2\): \(xy^{2}z=1^{a}1^{2b}1^{p-a-b}=0^{p}+1^{p}\) = \(1^{p+b}=0^{p}+1^{p}\). However, this string is not in \(ADD\), because this implies \(p+b=p\), but \(b>0\), a contradiction. Therefore, \(ADD\) is not regular.
- 1.55
The pumping lemma says that every regular language has a pumping length \(p\), such that every string in the language can be pumped if it has length \(p\) or more. If \(p\) is a pumping length for language \(A\), so is any length \(p^{\prime}\geq p\). The minimum pumping length for \(A\) is the smallest \(p\) that is a pumping length for \(A\). For example, if \(A=01^{*}\), the minimum pumping length is 2. The reason is that the string \(s=0\) is in \(A\) and has length 1 yet \(s\) cannot be pumped; but any string in \(A\) of length 2 or more contains a 1 and hence can be pumped by dividing it so that \(x=0,y=1\), and \(z\) is the rest. For each of the following languages, give the minimum pumping length and justify your answer.
- a. \(0001^{*}\) Solution: \alreadyanswered
- b. \(0^{*}1^{*}\) Solution: \alreadyanswered
- c. \(001\cup 0^{*}1^{*}\) Solution: We cannot pump \(001\), so the minimum pumping length is 4.
- d. \(0^{*}1^{+}0^{+}1^{*}\cup 10^{*}1\) Solution: \alreadyanswered
- e. \((01)^{*}\) Solution: We cannot pump \(\epsilon\), so the minimum pumping length is 1 (if we wanted to be constructive, the answer would be 2, since there is no string of length 1 here).
- g. \(1^{*}01^{*}01^{*}\) Solution: We cannot pump \(00\), but we can for \(100\), so the minimum pumping length is 3.

- 1.58 If \(A\) is any language, let \(A_{\frac{1}{3}-\frac{1}{3}}\) be the set of all strings in \(A\) with their middle thirds removed so that \(A_{\frac{1}{3}-\frac{1}{3}}=\{xz\;|\;\text{for some $y$, $|x|=|y|=|z|$ and $xyz\in A$}\}\). Show that if \(A\) is regular, then \(A_{\frac{1}{3}-\frac{1}{3}}\) is not necessarily regular. Solution: Let \(A=\{0^{*}\#1^{*}\}\), which is regular. Therefore, \(A_{\frac{1}{3}-\frac{1}{3}}\cap\{0^{*}1^{*}\}=\{0^{n}1^{n}\;|\;n\geq 0\}\) is also regular since regular languages are closed under intersection, and \(\{0^{*}1^{*}\}\) is a regular language. However, the resulting language is not regular, so therefore \(A_{\frac{1}{3}-\frac{1}{3}}\) is not necessarily regular when \(A\) is.
- 1.63
- (a) Let \(A\) be an infinite regular language. Prove that \(A\) can be split into two infinite disjoint regular subsets. Solution: since \(A\) is infinite and regular, then the conditions of the Pumping Lemma for Regular Languages hold, i.e., that there is a \(p\geq 0\) such that for all \(w\in A\), we can partition \(w\) into \(w=xyz\) that satisfy those 3 conditions. Consider \(A^{\prime}=\{xy^{2i}z\;|\;i\geq 0\}\), and \(A^{\prime\prime}=L\cap\overline{A^{\prime}}\). These are the desired languages because they partition \(A\) and are infinite.
- (b) Let \(B\) and \(D\) be two languages. Write \(B\Subset D\) if \(B\subseteq D\) and \(D\) contains infinitely many strings that are not in \(B\). Show that if \(B\) and \(D\) are two regular languages where \(B\Subset D\), then we can find a regular language \(C\) where \(B\Subset C\Subset D\). Solution: Let \(L=D\cap\overline{B}\); \(L\) is regular by the closure operations, and is infinite. By the Pumping Lemma for Regular Languages, there is a \(w\in L\) such that \(w=xyz\) such that \(|y|>0\), and for all \(i\geq 0\), \(xy^{i}z\in L\). Let \(C=B\cup\{xy^{i}z\in L\;|\;i\;\text{is even}\}\). Call the second language \(L^{\prime}\). We can see that \(C\) is regular. Since \(L^{\prime}\cap\overline{B}\) is infinite, we have \(B\Subset C\). By a similar analysis, we have \(C\Subset D\).

- 1.70
We define the
*avoids*operation for languages \(A\) and \(B\) to be \(A\)*avoids*\(B\) = {\(w\) \(|\) \(w\in A\) and \(w\) doesn’t contain any string in \(B\) as a substring}. Prove that the class of regular languages is closed under the*avoids*operation. Solution: The idea is to find a regular language that has strings in \(B\) as a substring, and remove from \(A\) this language. Therefore, define \(L_{substr}=\Sigma^{*}B\Sigma^{*}\). Clearly, \(L_{substr}\) is regular because it is the concatenation of 2 regular languages. Since regular languages are closed under complement and intersection, then \(A\setminus L_{substr}=A\cap\overline{L_{substr}}\) is also regular. But these are precisely the strings that are in \(A\) that are not in \(L_{substr}\), which is what we want. - 1.72
Let \(M_{1}\) and \(M_{2}\) be DFAs that has \(k_{1}\) and \(k_{2}\) states, respectively, and then let \(U=L(M_{1})\cup L(M_{2})\).
- a.
Show that if \(U\neq\emptyset\), then \(U\) contains some string \(s\), where \(|s|<\max(k_{1},k_{2})\).
Solution: Consider a DFA \(D=(Q,\Sigma,\delta,q_{0},F)\) such that \(L(D)\neq\emptyset\). Therefore, if the final state is reachable, transitioning from \(D\)’s start state to a final state requires at most \(|Q|-|F|\) transitions. Since \(U\neq\emptyset\), then either \(L(M_{1})\neq\emptyset\) or \(L(M_{2})\neq\emptyset\) (or both). We have the following cases:
- 1. \(L(M_{1})=\emptyset,L(M_{2})\neq\emptyset\). This implies that \(M_{1}\) has no reachable accept states, and \(M_{2}\) has at least one reachable accept state. Also, \(U=L(M_{2})\). From our observation above, if \(M_{2}\) accepts a string \(s\), then \(|s|\leq k_{2}-|F_{2}|<k_{2}\leq\max(k_{1},k_{2})\) where \(F_{2}\) is the set of accept states of \(M_{2}\). Therefore, \(s\in L(M_{2})=U\).
- 2. \(L(M_{1})\neq\emptyset,L(M_{2})=\emptyset\). This is equivalent to Case 1.
- 3.
\(L(M_{1}),L(M_{2})\neq\emptyset\). Therefore, \(M_{1}\) and \(M_{2}\) have at least one reachable accept state. Let \(s_{1}\) be the string of minimal length accepted by \(M_{1}\), and \(s_{2}\) for \(M_{2}\). Let \(s\in U\) be such that \(|s|=\min(|s_{1}|,|s_{2}|)\). We have the following 2 cases:
- 3.1. \(|s_{1}|\neq|s_{2}|\). This implies \(|s|=\min(|s_{1}|,|s_{2}|)<\max(|s_{1}|,|s_{2}|)\). There are two possibilities. If \(\max(|s_{1}|,|s_{2}|)=|s_{1}|\), then \(|s|=|s_{2}|<|s_{1}|<k_{1}\leq\max(k_{1},k_{2})\). Therefore, we are done. The same conclusion is reached if we consider when \(\max(|s_{1}|,|s_{2}|)=|s_{2}|\).
- 3.2. \(|s_{1}|=|s_{2}\). This implies \(|s|=\min(|s_{1}|,|s_{2}|)=\max(|s_{1}|,|s_{2}|)\). From our observation above, we have that \(|s|=\min(|s_{1}|,|s_{2}|)=\max(|s_{1}|,|s_{2}|)=|s_{1}|<k_{1}\leq\max(k_{1},k_{2})\). Therefore, we are done.

- b.
Show that if \(U\neq\Sigma^{*}\), then \(U\) excludes some string \(s\), where \(|S|<k_{1}k_{2}\).
Solution: Let \(D=(Q,\Sigma,\delta,q_{0},F)\) be a DFA such that \(L(D)=U=L(M_{1})\cup L(M_{2})\). Suppose (to the contrary) that all strings \(s\in U\) are such that \(|s|<k_{1}k_{2}\). Also, suppose there exists a non-accepting state \(q\in Q\). Therefore, there cannot exist a sequence of states \(q_{1},\cdots,q_{k_{1}k_{2}}\) in \(D\) such that running \(D\) on \(s\) would have \(q\) in this sequence:
- 1. \(q_{1}=q_{0}\).
- 2. \(\delta(q_{i},x)=q_{i+1}\) for \(1\leq i\leq k_{1}k_{2}-1\) and for all \(x\in\Sigma\).
- 3. \(q_{j}\neq q_{k}\) for \(j\neq k\).

- a.
Show that if \(U\neq\emptyset\), then \(U\) contains some string \(s\), where \(|s|<\max(k_{1},k_{2})\).
Solution: Consider a DFA \(D=(Q,\Sigma,\delta,q_{0},F)\) such that \(L(D)\neq\emptyset\). Therefore, if the final state is reachable, transitioning from \(D\)’s start state to a final state requires at most \(|Q|-|F|\) transitions. Since \(U\neq\emptyset\), then either \(L(M_{1})\neq\emptyset\) or \(L(M_{2})\neq\emptyset\) (or both). We have the following cases: