Product automaton construction

Prove Lemma 97 on p. 297.

Definition 126 (Product of automata): Let $\mathfrak {M}_{1}=(Q_{1}, \Sigma , P_{1}, q_{0}^{1}, F_{1})$ and $\mathfrak {M}_{2}=(Q_{2}, \Sigma , P_{2}, q_{0}^{2}, F_{2})$ be two finite automata with a common input alphabet $\Sigma$. A product of the automata $\mathfrak {M}_{1}$ and $\mathfrak {M}_{2}$ is any automaton $\mathfrak {N}$ of the form $\mathfrak {N}=(Q_{1} \times Q_{2}, \Sigma , P, (q_{0}^{1}, q_{0}^{2}), F)$, whose program $P$ contains the command $(q_{1}, q_{2}), a \rightarrow (p_{1}, p_{2})$ whenever $q_{1}, a \rightarrow p_{1} \in P_{1}$ and $q_{2}, a \rightarrow p_{2} \in P_{2}$. (No condition is imposed on the set of accepting states $F$ of $\mathfrak {N}$, so a product is not a uniquely determined operation — different choices of $F$ give different automata.)

Lemma 97: If $\mathfrak {N}$ is a product of $\mathfrak {M}_{1}$ and $\mathfrak {M}_{2}$, then for any two states $(q_{1}, q_{2})$ and $(p_{1}, p_{2})$ of $\mathfrak {N}$ and any input word $w$, the following holds: $w$ takes $(q_{1}, q_{2})$ to $(p_{1}, p_{2})$ in the automaton $\mathfrak {N}$ if and only if $w$ simultaneously takes $q_{1}$ to $p_{1}$ in $\mathfrak {M}_{1}$ and $q_{2}$ to $p_{2}$ in $\mathfrak {M}_{2}$.

Two languages are given over the alphabet $\Sigma =\left\{ a, b\right\}$:

For each of the following languages, use the product automaton method to construct a DFA that accepts the language:

For each of the following languages, construct a DFA that accepts the language:

Consider a Boolean function $f\left(a_{1}, a_{2}, \cdots , a_{n}\right)$. For any $n$ binary strings $x_{1}, x_{2}, \cdots , x_{n}$ of equal length, denote by $f\left(x_{1}, x_{2}, \cdots , x_{n}\right)$ the bitwise function $f$ on $x_{1}, x_{2}, \cdots , x_{n}$. That is, if $x_{i}=x_{i_{1}} x_{i_{2}} \ldots x_{i_{k}}$ for $i=1,2$, $\ldots , n$, where each $x_{i_{j}}$ is a bit in $\left\{ 0,1\right\}$, then $f\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ is equal to

Show that if languages $A_{1}, A_{2}, \cdots , A_{n}$ are regular, then language

is also regular.

The set of all binary strings having a substring 00 or ending with 01.

The set of all binary strings having a substring 00 and ending with 01.

The set of all binary strings having a substring 00 but not ending with 01.

Show that if $A$ and $B$ are regular languages over $\left\{ 0,1\right\}$, then

is also regular.

Show that if $A$ is a regular language and $B$ is a context-free language, then $A \cap B$ is a context-free language.

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\}$.