construct the NFA N_a and N_{b ^{such that}}

(20 point) By using the standard standard proceduce as given in Lemma 1.55 (Sipser), construct the NFA Na and N, such that (Na) = L(R, ) and L(M) = L(%). (OU 00) . 1 + and Rb-+++. Show intermediate where Ra steps. LEMMA 1.55 If a language is described by a regular expression, then it is regular PROOF IDEA Say that we have a regular expression R describing some lan- guage A. We show how to convert R into an NFA recognizing A. By Corol- lary 1.40, if an NFA recognizes A then A is regular. PROOF Let's convert R into an NFA N. We consider the six cases in the formal definition of regular expressions 1. R-a for some a E . Then L(R) = {a), and the following NFA recog- nizes L(R). Note that this machine fits the definition of an NFA but not that of a DFA because it has some states with no exiting arrow for each possible input symbol. Of course, we could have presented an equivalent DFA here; but an NFA is all we need for now, and it is easier to describe. Formally, N (1,q2),, , , g2]), where we describe 6 by saying that (a , a) = {G2} and that (r, b) = for rqi or ba. 2. R-e. Then L(R) , and the following NFA recognizes L(R). Formally, N-({q1), , , q1, {q1), where (r, b)-0 for any r and b 3. R-0. Then L(R) -0, and the following NFA recognizes L(R). Formally, N-((g), , , q,0), where (r, b)-0 for any r and b. 5, R=R1 o R2. 6. R-Rt. For the last three cases, we use the constructions given in the proofs that the class of regular languages is closed under the regular operations. In other words we construct the NFA for R from the NFAs for R1 and R2 (or just R1 in case 6) and the appropriate closure construction