CS 332:Theory of Computation
Theory of Computation | homework代写 | 代写express – 这个题目属于一个计算理论的代写任务, 涵盖了编译等方面, 这个项目是homework代写的代写题目
Boston University February 4, 2021
homework 2 Due Thursday, February 11, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutionsby 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 two bonus problems.
- (The problem formerly known as HW1 Problem 5.) Consider the following state diagram of an NFANover alphabet{A,B}.
start q 0
q 1 q 2 q 3
q 4 q 5
B
A,B
A
A
B
B
A
(a) Give a formal description of the machineNas a 5-tuple.
(b) Does the machine accept the stringAAB?
(c) Does the machine accept the stringBBBA?
(d) Does the machine accept the stringAAA?
(e) What is the language recognized byN?
- Consider the following state diagram of an NFANover alphabet{A,B}.
start q^0 B q^1 q^2 q^3
B
A
A
(a) Consider runningNon inputBBA. Give examples (i) of a computation path that leadsNto
an accept state when run on this input, (ii) a computation path that leadsNto a reject state,
and (iii) a computation path that leadsNto fail before its read the entire input.
1
(b) What is the language recognized byN?
(c) Use the subset construction to convertNinto a DFA recognizing the same language. Give
the state diagram of this DFA only include states that are reachable from the start state.
- Think about, but do not hand in: A DFA or NFA can, in general, have zero, one, or many accept states. Show that every NFA can be converted into another NFA recognizing the same language, but which has exactly one accept state. (This is solved exercise 1.11 in Sipser if youd like to check your solution.) To hand in: Prove that this is not true for DFAs. That is, show that there is a regular language Lsuch that every DFA recognizingLrequires at least two accept states. Hint:IfLcontains the empty string, what can you say about the start state of any DFA recognizingL?
- On Monday, well show that the class of regular languages is closed under the star operation. This problem will help you investigate this property.
(a) LetA={w{ 0 , 1 }|wends with 1}. Give the state diagram of a 2-state NFANrecognizing
A.
(b) Give a simple description of the languageA.
(c) Consider the followingfailedattempt to construct an NFA recognizingA: Add antransition
from every accept state ofNto the start state, and make the start state an accept state. Draw
the state diagram of this NFA, and call itN.
(d) What isL(N)? Give an example of a stringwsuch thatwL(N), butw /A.
(e) Give the state diagram of an NFA thatdoesrecognizeA.
- (a) Given languagesA, B, define the languageMIX(A, B) by
MIX(A, B) ={x 1 y 1 x 2 y 2... xnyn|n 0 , xiA, yiB}.
Note that eachxi, yiis astring. Show that the class of regular languages is closed underMIX.
Hint: You dont need to construct an NFA recognizingMIX(A, B) if you can find a way to
express it in terms of other operations.
(b) Given a languageA over alphabet , define the language TAIL(A) = {y | xy
Afor somex}. Show that the regular languages are closed underTAIL.
Bonus Problems
- In this problem, you will show that in the worst case, the subset construction uses a number of states that is optimal up to a factor of 2.
(a) For a natural numberk, letRkbe the language over alphabet{ 0 , 1 }consisting of strings
wsuch that thekth symbol from the right ofwis a 0. Show thatRkis recognized by an
NFA withk+ 1 states.
(b) Show that every DFA recognizingRkrequires at least 2kstates.
- A coNFA is like an NFA, except it accepts an inputwif and only ifeverypossible state it could end up in when readingwis an accept state. (By contrast, an NFA acceptswiffthere existsan accept state it could end up in when readingw.) Show that the class of languages recognized by coNFAs is exactly the regular languages.