Exercises

ᴬ 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.