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

Ars Digita University Theory of Computation TopicsLanguages 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 TopicsMore 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 it seems. This is just some object that contains four other objects and a method. Which one is the method? Operations on Languages: Our friends PREFIX and MIN An example Proof. Just so you have a reference, well show you how to prove that Regular languages are closed under difference, ie. L1-L2 is regular if L1 and L2 are. Let M1 = (Q1, Sigma, delta1, q1, F1) accept L1, and let Let M2 = (Q2, Sigma, delta2, q2, F2) accept L2 Then M = (Q1xQ2, Sigma, delta, (q1,q2), F1 x(Q2-F2) accepts L1-L2 where delta(r1,r2,a) = (delta1(r1,a), delta2(r2,a)At this point you should give a few words of justification about why you think this new machine would accept L1-L2. If the mathematical notation is just way to much for you, just try to explain things in intuitively. Regular expressions If we run out of things to talk about :-)Generalized NFAs NFA + reg. ex. transitions = GNFA Converting NFAs to Regular expressions Converting Regular expressions to NFAs Problems to work on Write out the NFA corresponding to the language and convert to a DFA: All strings that end in 0. Same for all strings whose penultimate character is 0. If you like this sort of thing: same things for all strings that that have 0 as the third to the last character. One more if youd like the practice: All strings ending in 0,1 Write out the NFA corresponding to this state/transition table: 01-pp,qpqrrrs*sssHere the star means we have an accept state Write regular expressions for all strings that end in aaba. Where Sigma is just the usual alphabet. Do the same for all strings that do not contain a. Write a regular expression for the strings that contain the substring 0101, where Sigma = 0,1. Do the same for all strings that alternate between 0 and 1 and end in 0. Do the same for strings that alternate between 0 and 1. Hard problem: Write a regular expression for the strings over 0,1 that are divisible by 3. Hard Problem: Build an automaton that recognizes the strings that have the same number of zeros and ones. TopicsThe Java Computability Toolkit. More on Regular Expressions. GNFAs and converting an NFA to a regular expression. Converting a Regular Expression to an NFA. Diagonalization. The Pumping Lemma. Problems to work on (Warm up) Give one string that is in the language and one that is not: a*b* a(ba)*b a* + b* (b + aaa)* aba+bab Write a regular expression That accepts the set of all strings. That accepts the set of all strings not containing 00 as a substring. Convert to regular expressions: Convert to an NFA: (001)*(1+e) (01*0 + e + 00) (001)*(1+e)(01*0 + e + 00) How long does a string in the following language have to be before we are guaranteed to have a loop? Is the set of all strings that are palindromes regular? Why or why not? Show that the set of all strings of zeros that have length that is a perfect cube can not be described by a regular expression. TopicsHow to minimize DFAs and why one would. Turning a DFA into a Grammar Decision Problems. Some applications of Regular expressions Everything is a string / number. Problems to work on Why do we care about minimizing DFAs ? Minimize the following DFA. What Language does it generate? Minimize the following DFA. What Language does it generate? Minimize the following DFA. What Language does it generate? Give a regular grammar that generates the same language as the DFA in problem 2. Give a regular grammars that generates the same language as the following regular expressions: 010* a(ab + bc)* Is the following a valid argument? Why or why not? The language L = 0m1m 2n | m, n = 0 is not regular, since we already know that M = 0m 1m | m = 0 is not regular by the pumping lemma, and since L contains M it cannot therefore be regular. Prove that the language x2n | n = 0 is not regular. Give a decision algorithm which takes as input a regular language L and decides whether L contains the string . Give a decision algorithm which takes as input a regular language L and decides whether L equals the language Give a decision algorithm which takes as input a regular language L and decides whether L contains the language given by the regular expression 10*10*1 Miscellaneous problem: Eliminate the espilon transitons of this NFA, without converting it to a DFA (ie, figure out an easier way) Mildy Challenging and Surprising Problem: Let L be any language over the alphabet 0, not necessarily regular. Show that L* is regular. Wicked hard challenging problem: Describe a grammar that generates the language 0p | p is a prime TopicsDecision Problems Context free grammars. Problems to work on Decision Problems Finish the decision problems form the last recitation handout. CFG warmupGive a context free grammar that generates the language of palindromes w(0+1+epsilon)wR | w is in (0 + 1)* Give a context free grammar that generates every possible string over 0,1 Give a context free grammar that generates the language 0n1 0n 111 0m 1r where n, m, r = 0 Give a context free grammar that generates the language of all strings that contain 101. Give a context free grammar that generates the language of all strings with an equal number of zeros and ones. And/OrGive a context free grammar that generates the language that has equal numbers of 0s and 1s or contains 101. Give a context free grammar that generates the language that has equal numbers of 0s and 1s and contains 101. Complements Give a context free grammar that generates the language of all strings of the form 0m1n where n = m = 0. Give a context free grammar that generates the language of all strings of the form 0m1n where n m = 0. Give a context free grammar that generates the complement of the language 0*1*. Give a context free grammar that generates the language w | w is not equal to 0n1n for any choice of n Challenging problem: Give a context free grammar that generates the language w | w is not a palindrome TopicsRigorous proofs using the pumping lemma. More constructions with context free grammars. Chomsky Normal Form. Problems to work on Finish working on the CFG problems from the lst handout. (Warmup). Generate the grammar for 0*1(0+1)*. Using the grammar above, What are the leftmost and rightmost derivation for the strings 1001, 0011? What are the parse trees? (Text 2.13) Consider the following grammar. 1.2. S - TT | U3. T - 0T | T0 | 14. U - 0U00 | 15.Describe the language it generates. Chomsky Normal Form Put the following grammar in Chomsky Normal form. (Text 2.14) 5.6. A - BAB | B | epsilon7. B - 00 | espilon8.Put the following grammar in Chomsky Normal form. 9.10. A - BAB | B | BC11. B - 00 | epsilon12. C - AA13.Rigorous pumping lemma proofsProblems from previous handouts kindly reproduced here. Rigorously prove using the pumping lemma. Prove that the language x2n | n = 0 is not regular. Show that the set of all strings of zeros that have length that is a perfect cube can not be described by a regular expression. TopicsUsing regular expressions and context free grammars with Lex and Yacc to build complex programs quickly. A calculator example. Chomsky Normal Form (Finish problems on Chomsky Normal Form that we didnt get to last time, i.e. all of them ;-) Push Down Automata. Problems to work on Give a grammar for the language ai bj | i = j z A s 2. A - xb B yz3. B - cd A q | epsilonPlay around with this grammar and try to guess what a pumping lemma for CFGs might look like. Construct a PDA for 0n1n | n = 0 without looking at your notes. Construct a PDA for 0n1m0m1n | n,m = 0 TopicsToday well mainly catch up on all the problems from previous handouts we havent done yet. Aisde: Languages as infinitely long streams of bits, complexity and compression Leftmost and Rightmost derivations. Parse Trees. Chomsky Normal Form. What it is useful for. Converting a grammar to Chomsky normal form. Intro to the pumping lemma for context free languages. Languages and streams o bitsHere is a list (well, the beginning of a list) of all possible strings that can be made from the characters a and b. They are ordered so that all strings of length 1 come first, then strings of length 2 then strings of length 3, . etc. e a b aa ab ba bb aaa aab aba abb baa bab bba bbb aaaa aaab aaba aabb abaa abab abba abbb baaa baab baba babb bbaa bbab bbba bbbb aaaaa aaaab aaaba aaabb aabaa aabab aabba aabbb abaaa abaab ababa ababb abbaa abbab abbba abbbb baaaa baaab baaba baabb babaa babab babba babbb bbaaa bbaab bbaba bbabb bbbaa bbbab bbbba bbbbb aaaaaa aaaaab aaaaba aaaabb aaabaa aaabab aaabba aaabbb aabaaa aabaab aababa aababb aabbaa aabbab aabbba aabbbb abaaaa abaaab abaaba abaabb ababaa ababab ababba ababbb abbaaa abbaab abbaba abbabb abbbaa abbbab abbbba abbbbb baaaaa baaaab baaaba baaabb baabaa baabab baabba baabbb babaaa babaab bababa bababb babbaa babbab babbba babbbb bbaaaa bbaaab bbaaba bbaabb bbabaa bbabab bbabba bbabbb bbbaaa bbbaab bbbaba bbbabb bbbbaa bbbbab bbbbba bbbbbbA language is an infinite stream of bits. Example a(a+b)* 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Example (ab)* 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Problems to work on Work on the problems from previous handouts TopicsHow many languages are there? Nondeterministic Pushdow