These two questions are related to DFA and NFA

4. Given any string w {0, 1}, let n0(w) = number of 0s in w and n1(w) = number of 1s in w.

Prove, by using the pumping lemma, that the language{w | 0 n0(w) 2n1(w)+1.}

is not a regular language.

3. (25 point) Apply the technique as shown in Chapter 1, section 3 (Sipser) to convert the NFA Na to an equivalent regular expression Rd Your answer should provide, all the intermediate steps as in the example 1.68 from our text 0 0 0 ql q2 q3 Figure 1: The NFA Na, where e repre- sent the empty string 3. (25 point) Apply the technique as shown in Chapter 1, section 3 (Sipser) to convert the NFA Na to an equivalent regular expression Rd Your answer should provide, all the intermediate steps as in the example 1.68 from our text 0 0 0 ql q2 q3 Figure 1: The NFA Na, where e repre- sent the empty string