1. (32%) Give an NFA for the language of strings that contain 1001 as a substring....

 

Transcribed Image Text:

1. (32%) Give an NFA for the language of strings that contain 1001 as a substring. Use no more than five states and eight transitions. (Transitions labeled with two symbols count as two transitions.) 2. (32%) Give an NFA for the language of strings that begin with 00 and end in 11. Use no more than five states and six transitions. 3. (36%) Give a formal description of the following NFA. Describe the tran- sition function by using a table. 91 0,1 0 0, 40 1, E 92 93 1. (36%) Convert the following NFA into an equivalent DFA. 1 0,1 0 0 90 91 92 0 2. (32%) Convert the following NFA into an equivalent DFA. 1 90 0,8 1 0 41 92 0 1. (32%) Give an NFA for the language of strings that contain 1001 as a substring. Use no more than five states and eight transitions. (Transitions labeled with two symbols count as two transitions.) 2. (32%) Give an NFA for the language of strings that begin with 00 and end in 11. Use no more than five states and six transitions. 3. (36%) Give a formal description of the following NFA. Describe the tran- sition function by using a table. 91 0,1 0 0, 40 1, E 92 93 1. (36%) Convert the following NFA into an equivalent DFA. 1 0,1 0 0 90 91 92 0 2. (32%) Convert the following NFA into an equivalent DFA. 1 90 0,8 1 0 41 92 0