CS 332: Theory of Computation Prof. Boston University September 14, 2021
Homework 2 – Due Tuesday, September 21, 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 6 required problems and two bonus problems.
Copyright By PowCoder代写 加微信 powcoder
1. Consider the following state diagram of an NFA N over alphabet {A, B}.
(a) Give a formal description of the machine N as a 5-tuple. (b) Does the machine accept the string BBAA?
(c) Does the machine accept the string BBABBB? (d) Does the machine accept the string BAAB?
(e) What is the language recognized by N?
2. Consider the following state diagram of an NFA N over alphabet {A, B}.
start q0 ε q1 B q2 B q3
(a) Consider running N on input AABB. Give examples (i) of a computation path that leads N to an accept state when run on this input, (ii) a computation path that leads N to a reject state, and (iii) a computation path that leads N to fail before it’s read the entire input.
(b) What is the language recognized by N?
(c) Use the subset construction to convert N into a DFA recognizing the same language. Give
the state diagram of this DFA – only include states that are reachable from the start state.
3. (NFAs can be simpler than DFAs) Consider the language L = {w ∈ {0, 1}∗ | w does not
contain both 0 and 1}.
(a) Give the state diagram of an NFA recognizing L that has exactly one accept state.
(b) Prove that every DFA recognizing L requires at least two accept states.
4. (Closure care) On Thursday, we’ll show that the class of regular languages is closed under the star operation. This problem will help you investigate this property.
Let A = {w ∈ {0, 1}∗ | w contains the symbol 1}. Give the state diagram of a 2-state DFA D recognizing A.
Give a simple description of the language A∗.
Consider the following failed attempt to construct an NFA recognizing A∗: Add an ε transition from every accept state of D to the start state, and make the start state an accept state. Draw the state diagram of this NFA, and call it N.
What is L(N)? Give an example of a string w such that w ∈ L(N), but w ∈/ A∗. Give the state diagram of an NFA that does recognize A∗.
For a string w ∈ {0,1}∗, define the inversion INV(w) to be the string where 0’s in w are replaced by 1’s and 1’s are replaced by 0’s. Given a language L ⊆ {0, 1}∗, define the language INV(L) = {w | INV(w) ∈ L}. Show that the class of regular languages is closed under INV.
Given languages A and B over the same alphabet Σ, define the language A \ B = {w ∈ Σ∗ | w ∈ A but w ∈/ B}. Show that the regular languages are closed under the operation “\”.
6. (Regex to description) Give plain English descriptions of the languages generated by each of the following regular expressions
(a) b(ab)∗
(b) (0∪1)((0∪1)(0∪1)(0∪1))∗
(c) (a∪b)∗ ∪(b∪c)∗ (d) ε∗
Bonus Problems
1. Given a language L over alphabet Σ, define the language cdr(L) = {y ∈ Σ∗ | ay ∈ L for some a ∈ Σ}. Show that the regular languages are closed under cdr.1
2. A coNFA is like an NFA, except it accepts an input w if and only if every possible state it could end up in when reading w is an accept state. (By contrast, an NFA accepts w iff there exists an accept state it could end up in when reading w.) Show that the class of languages recognized by coNFAs is exactly the regular languages.
1https://www.gnu.org/software/emacs/manual/html_node/eintr/car-_0026-cdr.html 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com