Question 1.44: Let B and C be languages over Σ= {0, 1}. Define

Let $M_{B} = (Q_{B},\Sigma , \delta _{B},q_{B} ,F_{B} )$ and $M_{C} = (Q_{C},\Sigma , \delta _{C},q_{B} ,F_{C} )$ be DFAs recog-nizing B and C, respectively. Construct NFA $M = (Q,\Sigma ,\delta ,q_{0} ,F)$ that recognizes $B \xleftarrow[]{1} C$ as follows. To decide whether its input ω is in $B \xleftarrow[]{1} C$, the machine M checks that ω ∈ B, and in parallel nondeterministically guesses a string y that contains the same number of 1s as contained in w and checks that y ∈ C.

$Q = Q_{B}\times Q_{C}$.
For $(q,r) \in Q$ and $a\in \Sigma _{\epsilon }$, define

$\delta((q, r), a)= \begin{cases}\left\{\left(\delta_{B}(q, 0), r\right)\right\} & \text { if } a=0 \\ \left\{\left(\delta_{B}(q, 1), \delta_{C}(r, 1)\right)\right\} & \text { if } a=1 \\ \left\{\left(q, \delta_{C}(r, 0)\right)\right\} & \text { if } a=\varepsilon\end{cases}$
3. $q_{0}=\left(q_{B}, q_{C}\right)$.
4. $F=F_{B} \times F_{C}$.