CS 332: Theory of Computation Prof. Boston University September 22, 2021
Homework 3 – Due Tuesday, September 28, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as- sistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problems There are 5 required problems and 1 bonus problem. Problem 1 will be autograded by AutomataTutor.
Copyright By PowCoder代写 加微信 powcoder
1. (Regular expressions vs. finite automata) Please log on to AutomataTutor to submit solutions for this question.
(a) (Description to regex) Give regular expressions generating the following languages: i. {w ∈ {0,1}∗ | w has exactly one 0 and at least two 1’s}.
ii. {w ∈ {0, 1}∗ | w is any string except for 00 or 000}.
iii. {w ∈ {0, 1}∗ | w starts with 0 and has even length or w starts with 1 and has odd length}.
(b) (Regex to NFA) Use the procedure described in class (also in Sipser, Lemma 1.55) to convert ((A ∪ C)∗(T ∪ G)∗(TA ∪ TG))∗ to an equivalent NFA. Simplify your NFA.
(c) (NFA to regex) Convert the following NFA (over alphabet {A, B}) to an equivalent regular expression.
2. (The fault in our stars)
(a) If A and B are finite languages, what is the maximum cardinality of A ∪ B? What is the
maximum cardinality of A ◦ B? Explain your answers.
(b) A star-free regular expression is a regex using only the symbols ∅, ε, ∪, ◦, and alphabet symbols in R. The size of a star-free regex is the number of such symbols it contains. (That is, do not count parentheses.) For a natural number k, let S(k) denote the maximum number of elements in the language generated by a star-free regex R of size k. Prove by induction on k that S(k) ≤ 22k .
(c) Conclude that a star-free regex always generates a finite language.
3. (Regex complement)
Explain how you could design an algorithm that, given a regex R, constructs a regex S such that L(S) = L(R). You may assume you have access to functions such as RegexToNFA, NFAToRegex, NFAtoDFA, etc. implementing the constructions we’ve seen in class. For example, NFAtoDFA takes as input an NFA and uses the subset construction to return an equivalent DFA. You can assume these functions handle low-level details like parsing parentheses for you. You can also use functions performing the other constructions we’ve seen in class; just either give a precise reference to the slides or the textbook, or a 1-2 sentence description of the construction to make it completely clear what you are referring to.
4. (Distinguishing set method) Let Σ = {a, b}. For each k ≥ 1, let Ck be the language consisting of all strings that contain an a exactly k places from the right-hand end. That is, Ck = {wax1 . . . xk−1 | w ∈ Σ∗,x1,…,xk−1 ∈ Σ}.
(a) Describe an NFA with k + 1 states that recognizes Ck in terms of both a state diagram and a formal description.
(b) Prove that Ck has a pairwise distinguishable set of size 2k.
(c) Use part (b) to conclude that no DFA with fewer than 2k states can recognize Ck.
(d) Could there be an NFA with fewer than k states recognizing Ck? Explain your answer.
5. (Non-regular languages) Prove that the following languages are not regular. You may only use the distinguishing set method and the closure of the class of regular languages under union, intersection, complement, and reverse.
(a) L1 ={0n1m |n,m≥0andn=m2}.
(b) L2 ={0n1m0n |m,n≥0}.
(c) L3 = 1ky | y ∈ 0,1∗ and |y| = k.
(d) L4 =aibjck |i,j,k≥0andifi=1thenj=k.
(e) LetΣ={0,1,+,=}. LetL5 ={x+y=z|x,y,zarebinarynonnegativeintegersandx+y= z}.
6. (Bonus problem) Prove that for every natural number n, there is a language Bn such that a) Bn is recognizable by an NFA with n + 1 states, but b) If Bn = A1 ∪ ··· ∪ Ak for regular languages A1,…,Ak, then at least one of the languages Ai requires a DFA with at least 2n/k states.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com