3. Consider the NFAs N (on the left) and N (on the right): DO q2 q4...

 

Transcribed Image Text:

3. Consider the NFAs N (on the left) and N (on the right): DO q2 q4 XQ q1 q2 (N is described in example 1.33 on page 52.) (a) Write out the formal definition of N and N. Notice that N appears to be a DFA but we are asking for its formal description as a NFA. Be careful of types, especially when describing the transition function of each NFA. (b) Write out L(N) and L(N) in set builder notation, justifying each briefly by making specific references to the state diagrams. (c) In fact, L(N) = L(N). You can check this by using the "test equivalence" feature of JFLAP to compare the two state diagrams. Explain why these two NFAs are equivalent. 3. Consider the NFAs N (on the left) and N (on the right): DO q2 q4 XQ q1 q2 (N is described in example 1.33 on page 52.) (a) Write out the formal definition of N and N. Notice that N appears to be a DFA but we are asking for its formal description as a NFA. Be careful of types, especially when describing the transition function of each NFA. (b) Write out L(N) and L(N) in set builder notation, justifying each briefly by making specific references to the state diagrams. (c) In fact, L(N) = L(N). You can check this by using the "test equivalence" feature of JFLAP to compare the two state diagrams. Explain why these two NFAs are equivalent.