1. Construct DFAs that recognize the following languages over the alphabet {a,b}: (a) {w; w contains...

Transcribed Image Text:

1. Construct DFAs that recognize the following languages over the alphabet {a,b}: (a) {w; w contains exactly two b's, or an even number of a's} (b) {ww contains as substring ababb and/or bbb }. (c) {w w is any string except the two strings abba and aba} Draw the state diagram for all; add a formal description of the DFA for (b), and add a proof that your DFA recognizes exactly the specified language for (c)). To do this, you will need to prove that (1) your DFA accepts all strings in the language and (2) any string accepted is in the language. 2. Problem 1.16 (a) page 86 of the textbook Sipser - second edition (convert NFA to DFA). Please see the scan on Blackboard. Show intermediate steps, if any. 3. For each of the following give two strings that are members of the language, and two strings that are not members of the language. Assume the alphabet = = {0, 1}. 1. *00*12*. 2. (1 U10 U00)* 3. (111)*. 4. Give regular expressions generating the languages of Exercise 1. For (a), prove (by induction) that the language of your expression is equal to the language as described in (a). 5. Problem 1.21(a) page 86 of the textbook Sipser - second edition (convert DFA to regular expres- sion). Please see the scan on Blackboard. Show intermediate steps, if any. 6. Construct state diagrams of NFA's accepting languages specified by the following regular expres- sions: 1. (21)* U2* 2. (213)*2* 3. (12 U11)* (21 U 22)* 1. Construct DFAs that recognize the following languages over the alphabet {a,b}: (a) {w; w contains exactly two b's, or an even number of a's} (b) {ww contains as substring ababb and/or bbb }. (c) {w w is any string except the two strings abba and aba} Draw the state diagram for all; add a formal description of the DFA for (b), and add a proof that your DFA recognizes exactly the specified language for (c)). To do this, you will need to prove that (1) your DFA accepts all strings in the language and (2) any string accepted is in the language. 2. Problem 1.16 (a) page 86 of the textbook Sipser - second edition (convert NFA to DFA). Please see the scan on Blackboard. Show intermediate steps, if any. 3. For each of the following give two strings that are members of the language, and two strings that are not members of the language. Assume the alphabet = = {0, 1}. 1. *00*12*. 2. (1 U10 U00)* 3. (111)*. 4. Give regular expressions generating the languages of Exercise 1. For (a), prove (by induction) that the language of your expression is equal to the language as described in (a). 5. Problem 1.21(a) page 86 of the textbook Sipser - second edition (convert DFA to regular expres- sion). Please see the scan on Blackboard. Show intermediate steps, if any. 6. Construct state diagrams of NFA's accepting languages specified by the following regular expres- sions: 1. (21)* U2* 2. (213)*2* 3. (12 U11)* (21 U 22)*