浙江大学计算理论期末考试考博复习提纲和练习.doc

Ars Digita University Theory of Computation Topics Languages All computational problems can be reframed as questions of membership in a language (set). Drawing Deterministic Finite Automata (DFAs). Drawing Nondeterministic Finite Automata (NFAs). Converting NFAs to DFAs Regular Languages, Closure properties of Regular languages. Problems to work on What is a language? Draw a DFA that accepts the strings ending in 01. Draw a DFA that accepts the strings that have an even number of zeros. Draw a DFA that accepts the strings that have an even number of zeros or end in 01. Draw a DFA that accepts the strings that have an even number of zeros and end in 01. Draw a DFA that accepts the strings that have an even number of zeros but dont end in 01. Draw an NFA that accepts the strings that end in 01. Try to make it as simple as possible. Draw an NFA that accepts the strings that have an even number of zeros or end in 01 using six states. Draw an NFA that accepts any string that is a concatenation of a string that has an even number of zeros with a string that ends in 01. Draw an NFA that accepts the strings that have an even number of zeros and end in 01. Draw an NFA that accepts the language 0, using only two states. Convert the previous NFA into a DFA using the method described in class. Draw an NFA with two states that corresponds to the language 0?2*. Convert the previous NFA to a DFA. What is a regular language? Draw the DFA that corresponds to the language 10*10*. What is the Prefix of the language corresponding to the language 10*10*. Draw the DFA for the prefix of the language corresponding to the regular expression 10*10*. What is the MIN of the language 10*10*? Draw the DFA corresponding to the MIN of the language 10*10*. Main Topics More practice with NFAs, Converting to DFAs, getting rid of epsilons. Formal defintion of Automata The math mumbo-jumbo formulation is: Some five-tuple (Q, Sigma, delta, q, F).... But thats not as bad as