Midterm9532.dvi Midterm COSC 3335 – Automata and Formal Languages Student Name: Problem 1 [10 pts] Prove that for all x 1: Problem 2 [10 pts] Construct a DFA that recognizes the following languages....

Course is Theory of Computation


Midterm9532.dvi Midterm COSC 3335 – Automata and Formal Languages Student Name: Problem 1 [10 pts] Prove that for all x 1: Problem 2 [10 pts] Construct a DFA that recognizes the following languages. For each case the alphabet is {0,1}. NOTE: You must provide the formal definition of the DFA, as well as its state transition diagram. a) A1 = {w||w|%4 = 0} b) A2 = {w| w contains 0101 as substring } Problem 3 [20 pts] Using the closure properties of regular languages and Deterministic Finite Automata, construct DFAs that recognize the following languages. For each case the alphabet is {0,1}. NOTE: You must provide the formal definition of the DFA, as well as its state transition diagram for each DFA. a) A1 = {w| 010 is not a substring of w} b) A2 = {w|w starts with 01 and ends with 10 } Problem 4 [30 pts] For each of the following languages construct an NFA with the specified number of states. For each case the alphabet is {0,1}. NOTE: You must provide the formal definition of the NFA, as well as its state transition diagram. a) A1 = {w| w ends with 10 } with three states. b) A2 = {w| w contains substring 1011 } with five states. c) A3 = {w| w contains an odd number of 1s and exactly two 0s } with six states. Problem 5 [20 pts] Convert the following NFA to an equivalent DFA. Show all your work. a 1 2 3 ,b a a b Problem 6 [10 pts] Prove that if two languages A and B are regular, then the language A−B is regular.