Regular Languages

ᴬ The following are the state diagrams of two DFAs, $M_{1}$ and $M_{2}$. Answer the following questions about each of these machines.

ᴬ Give the formal description of the machines $M_{1}$ and $M_{2}$ pictured in Exercise 1.1.

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

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 =\left\{ \mathrm{a}, \mathrm{b}\right\}$.

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 =\left\{ \mathrm{a}, \mathrm{b}\right\}$.

Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is $\left\{ 0,1\right\}$.

Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is $\left\{ 0,1\right\}$.

Use the construction in the proof of Theorem 1.45 to give the state diagrams of NFAs recognizing the union of the languages described in

Use the construction in the proof of Theorem 1.47 to give the state diagrams of NFAs recognizing the concatenation of the languages described in

Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described in

ᴬ Prove that every NFA can be converted to an equivalent one that has a single accept state.

Let $D=\left\{ w \mid w\text{ contains an even number of a's and an odd number of b's and does not contain the substring ab}\right\}$. Give a DFA with five states that recognizes $D$ and a regular expression that generates $D$. (Suggestion: Describe $D$ more simply.)

Let $F$ be the language of all strings over 0,1 that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes $F$. (You may find it helpful first to find a 4-state NFA for the complement of $F$.)

Give a counterexample to show that the following construction fails to prove Theorem 1.49, the closure of the class of regular languages under the star operation. ¹ Let $N_{1}=\left(Q_{1}, \Sigma , \delta_{1}, q_{1}, F_{1}\right)$ recognize $A_{1}$. Construct $N=\left(Q_{1}, \Sigma , \delta , q_{1}, F\right)$ as follows. $N$ is supposed to recognize $A_{1}^{*}$.

Use the construction given in Theorem 1.39 to convert the following two nondeterministic finite automata to equivalent deterministic finite automata.

Give regular expressions generating the following languages (cf. Exercise 1.6). In all parts, the alphabet is $\left\{ 0,1\right\}$.

Use the procedure described in Lemma 1.60 to convert the following finite automata to regular expressions.

In certain programming languages, comments appear between delimiters such as / and /. Let $C$ be the language of all valid delimited comment strings. A member of $C$ must begin with / and end with / but have no intervening /. For simplicity, assume that the alphabet for $C$ is $\Sigma =\left\{ \mathrm{a}, \mathrm{b}, /, \# \right\}$.

ᴬ Let $B$ be any language over the alphabet $\Sigma$. Prove that $B=B^{+}$iff $B B \subseteq B$.

A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject. The following are state diagrams of finite state transducers $T_{1}$ and $T_{2}$.

Each transition of an FST is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol. The two symbols are written with a slash, /, separating them. In $T_{1}$, the transition from $q_{1}$ to $q_{2}$ has input symbol 2 and output symbol 1. Some transitions may have multiple input-output pairs, such as the transition in $T_{1}$ from $q_{1}$ to itself. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol. For example, on input 2212011, machine $T_{1}$ enters the sequence of states $q_{1}, q_{2}, q_{2}, q_{2}, q_{2}, q_{1}, q_{1}, q_{1}$ and produces output 1111000. On input abbb, $T_{2}$ outputs 1011. Give the sequence of states entered and the output produced in each of the following parts.

Read the informal definition of the finite state transducer given in Exercise 1.24. Give a formal definition of this model, following the pattern in Definition 1.5 (page 35). Assume that an FST has an input alphabet $\Sigma$ and an output alphabet $\Gamma$ but not a set of accept states. Include a formal definition of the computation of an FST. (Hint: An FST is a 5-tuple. Its transition function is of the form $\delta : Q \times \Sigma \longrightarrow Q \times \Gamma$.)

Exercise 1.24: A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject. Each transition of an FST is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol, with the two symbols written with a slash, /, separating them. Some transitions may have multiple input-output pairs. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol.

Using the solution you gave to Exercise 1.25, give a formal description of the machines $T_{1}$ and $T_{2}$ depicted in Exercise 1.24.

Read the informal definition of the finite state transducer given in Exercise 1.24. Give the state diagram of an FST with the following behavior. Its input and output alphabets are $\left\{ 0,1\right\}$. Its output string is identical to the input string on the even positions but inverted on the odd positions. For example, on input 0000111 it should output 1010010.

Exercise 1.24: A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject. Each transition of an FST is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol, with the two symbols written with a slash, /, separating them. Some transitions may have multiple input-output pairs. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol.

Convert the following regular expressions to NFAs using the procedure given in Theorem 1.54. In all parts, $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$.

Use the pumping lemma to show that the following languages are not regular.

Describe the error in the following "proof" that $0^{*} 1^{*}$ is not a regular language. (An error must exist because $0^{*} 1^{*}$ is regular.) The proof is by contradiction. Assume that $0^{*} 1^{*}$ is regular. Let $p$ be the pumping length for $0^{*} 1^{*}$ given by the pumping lemma. Choose $s$ to be the string $0^{p} 1^{p}$. You know that $s$ is a member of $0^{*} 1^{*}$, but Example 1.73 shows that $s$ cannot be pumped. Thus you have a contradiction. So $0^{*} 1^{*}$ is not regular.

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}}=\left\{ w^{\mathcal{R}} \mid w \in A\right\}$. Show that if $A$ is regular, so is $A^{\mathcal{R}}$.

Let

$\Sigma_{3}$ contains all size 3 columns of 0s and 1s. A string of symbols in $\Sigma_{3}$ gives three rows of 0s and 1s. Consider each row to be a binary number and let

For example,

Show that $B$ is regular. (Hint: Working with $B^{\mathcal{R}}$ is easier. You may assume the result claimed in Problem 1.31.)

Let

Here, $\Sigma_{2}$ contains all columns of 0s and 1s of height two. A string of symbols in $\Sigma_{2}$ gives two rows of 0 s and 1 s. Consider each row to be a binary number and let

For example, $\left[\begin{array}{l}0 \\ 0\end{array}\right]\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}1 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 0\end{array}\right] \in C$, but $\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}1 \\ 0\end{array}\right] \notin C$. Show that $C$ is regular. (You may assume the result claimed in Problem 1.31.)

Let $\Sigma_{2}$ be the same as in Problem 1.33. Consider each row to be a binary number and let

Problem 1.33: $\Sigma_{2}$ contains all columns of 0s and 1s of height two,

A string of symbols in $\Sigma_{2}$ gives two rows of 0s and 1s. For example, $\left[\begin{array}{l}0 \\ 0\end{array}\right]\left[\begin{array}{l}1 \\ 0\end{array}\right]\left[\begin{array}{l}1 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 0\end{array}\right] \in D$, but $\left[\begin{array}{l}0 \\ 0\end{array}\right]\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}1 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 0\end{array}\right] \notin D$. Show that $D$ is regular.

Let $\Sigma_{2}$ be the same as in Problem 1.33. Consider the top and bottom rows to be strings of 0s and 1s, and let

Problem 1.33: $\Sigma_{2}$ contains all columns of 0s and 1s of height two,

A string of symbols in $\Sigma_{2}$ gives two rows of 0s and 1s. Show that $E$ is not regular.

Let $B_{n}=\left\{ \mathrm{a}^{k} \mid k \text{ is a multiple of } n\right\}$. Show that for each $n \geq 1$, the language $B_{n}$ is regular.

Let $C_{n}=\left\{ x \mid x\text{ is a binary number that is a multiple of }n\right\}$. Show that for each $n \geq 1$, the language $C_{n}$ is regular.

An all-NFA $M$ is a 5-tuple $\left(Q, \Sigma , \delta , q_{0}, F\right)$ that accepts $x \in \Sigma^{*}$ if every possible state that $M$ could be in after reading input $x$ is a state from $F$. Note, in contrast, that an ordinary NFA accepts a string if some state among these possible states is an accept state. Prove that all-NFAs recognize the class of regular languages.

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 \left\{ 0,1\right\}^{*}$ exists that is recognized by a DFA with $k$ states but not by one with only $k-1$ states.

Recall that string $x$ is a prefix of string $y$ if a string $z$ exists where $x z=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.

For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language

Show that the class of regular languages is closed under perfect shuffle.

For languages $A$ and $B$, let the shuffle of $A$ and $B$ be the language

Show that the class of regular languages is closed under shuffle.

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

ᴬ Let $B$ and $C$ be languages over $\Sigma =\left\{ 0,1\right\}$. Define $B \stackrel{1}{\leftarrow } C=\left\{ w \in B \mid \text{ for some }y \in C\text{, strings }w\text{ and }y\text{ contain equal numbers of 1 s }\right\}$. Show that the class of regular languages is closed under the $\stackrel{1}{\leftarrow }$ operation.

• Let $A / B=\left\{ w \mid w x \in A\text{ for some }x \in B\right\}$. Show that if $A$ is regular and $B$ is any language, then $A / B$ is regular.

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement.

Let $\Sigma =\left\{ 1, \# \right\}$ and let $Y=\left\{ w \mid w=x_{1} \# x_{2} \# \cdots \# x_{k} \text{ for } k \geq 0, \text{ each } x_{i} \in 1^{*}, \text{ and } x_{i} \neq x_{j} \text{ for } i \neq j\right\}$. Prove that $Y$ is not regular.

Let $\Sigma =\left\{ 0,1\right\}$ and let $D=\left\{ w \mid w\text{ contains an equal number of occurrences of the substrings 01 and 10}\right\}$. Thus $101 \in D$ because 101 contains a single 01 and a single 10, but $1010 \notin D$ because 1010 contains two 10 s and one 01. Show that $D$ is a regular language.

ᴬ 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 $\left\{ 0,1\right\}$.

Exercise 1.24: A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject. Each transition of an FST is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol, with the two symbols written with a slash, /, separating them. Some transitions may have multiple input-output pairs. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol.

Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are distinguishable by $\boldsymbol {L}$ if some string $z$ exists whereby exactly one of the strings $x z$ and $y z$ is a member of $L$; otherwise, for every string $z$, we have $x z \in L$ whenever $y z \in L$ and we say that $x$ and $y$ are indistinguishable by $\boldsymbol {L}$. If $x$ and $y$ are indistinguishable by $L$, we write $x \equiv_{L} y$. Show that $\equiv_{L}$ is an equivalence relation.

ᴬ 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 $\boldsymbol {L}$ if every two distinct strings in $X$ are distinguishable by $L$. Define the index of $\boldsymbol {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.

Problem 1.51: We say that strings $x$ and $y$ are distinguishable by $\boldsymbol {L}$ if some string $z$ exists whereby exactly one of the strings $x z$ and $y z$ is a member of $L$; otherwise, for every string $z$, we have $x z \in L$ whenever $y z \in L$ and we say that $x$ and $y$ are indistinguishable by $\boldsymbol {L}$.

Let $\Sigma =\left\{ 0,1,+,=\right\}$ and

Show that $\operatorname {ADD}$ is not regular.

Consider the language $F=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0 \text{ and if } i=1 \text{ then } j=k\right\}$.

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.

• If $A$ is a set of natural numbers and $k$ is a natural number greater than 1, let

Here, we do not allow leading 0s in the representation of a number. For example, $B_{2}(\left\{ 3,5\right\} )=\left\{ 11,101\right\}$ and $B_{3}(\left\{ 3,5\right\} )=\left\{ 10,12\right\}$. Give an example of a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular. Prove that your example works.

• If $A$ is any language, let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that

Show that if $A$ is regular, then so is $A_{\frac{1}{2}-}$.

• 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

Show that if $A$ is regular, then $A_{\frac{1}{3}-\frac{1}{3}}$ is not necessarily regular.

• Let $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$ be a DFA and let $h$ be a state of $M$ called its "home". A synchronizing sequence for $M$ and $h$ is a string $s \in \Sigma^{*}$ where $\delta (q, s)=h$ for every $q \in Q$. (Here we have extended $\delta$ to strings, so that $\delta (q, s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$.) Say that $M$ is synchronizable if it has a synchronizing sequence for some state $h$. Prove that if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^{3}$. Can you improve upon this bound?

Let $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. For each $k \geq 1$, let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end. Thus $C_{k}=\Sigma^{*} \mathrm{a} \Sigma^{k-1}$. Describe an NFA with $k+1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description.

Consider the languages $C_{k}$ defined in Problem 1.60. Prove that for each $k$, no DFA can recognize $C_{k}$ with fewer than $2^{k}$ states.

Problem 1.60: Let $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. For each $k \geq 1$, let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end. Thus $C_{k}=\Sigma^{*} \mathrm{a} \Sigma^{k-1}$.

Let $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. For each $k \geq 1$, let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols. Thus $D_{k}=\Sigma^{*} \mathrm{a}(\Sigma \cup \varepsilon )^{k-1}$. Describe a DFA with at most $k+1$ states that recognizes $D_{k}$ in terms of both a state diagram and a formal description.

Let $N$ be an NFA with $k$ states that recognizes some language $A$.