” 写作CSCI3136编程实验、Java，Python，CSS程序 辅导Assignment 2Instructor: Alex BrodskyDue: 9:00am, Monday, May 28, 20211. Construct NFAs that recognize the languages specified by the following regular expressions:(a) [5 marks] 000 (101 | 010)* (011 | 110 | 111)where the alphabet is = {0, 1}.(b) [5 marks] ((x* y z*) | (y* z y*) | (z* x y*)where the alphabet is = {x, y, z}.2. [10 marks] Construct a DFA that Recognizes the same language as the following NFA. Hint,use the subset construction approach we discussed in Lecture 5.Note: You do not need to draw it. I.e, you can just provide the table representing thetransition function for the DFA.3. [10 marks] Derive the regular Expression that specifies the language recognzied by this NFA.1CSCI3136 Summer 2021 Assignment 24. For each of the following give two (2) different constructions as specified below:(a) [3 marks] Give two different regular expressions that specify the language L3, the setof all strings over the alphabet = {x} whose length is divisible by 3. Note: please donot use the . in your regular Expressions as there is only one symbol in the alphabet.(b) [3 marks] Give two different NFAs that recognize the language specified by the regularexpression(x (x|y)* x) | (y (x|y)* y)over the alphabet = {x, y}.(c) [4 marks] Give two DFAs that recognize the same languages as this NFA.5. Using the basic definition of regular languages prove that the following two languages areregular:(a) [5 marks] The language Lnot3 of all strings over alphabet = {x} that are notdivisible by 3.(b) [5 marks] The language L = LQLeven where LQ = {ap1| p PRIME} and Leven ={(aa)}. Note: You may recall from our lectures that the language of prime-lengthstrings is not regular, yet rest assured that L is definitely regular. (This is the hardestquestion in this assignment.) Hint: You will need to use a very simple property of almostall prime numbers to prove this.2CSCI3136 Summer 2021 Assignment 2Marking Scheme1. Marking scheme for each part of Question 1.2 points 1 point 0 pointsStates Correct # of States 1 or 2 states missing IncorrectTransitions Correct Somewhat correct IncorrectCorrectness Recognizes the langauge Does not recognize the language2. Marking scheme for Question 2.4 points 2 point 0 pointsStates Correct # of states 1 or 2 states missing IncorrectTransitions Correct Somewhat correct IncorrectCorrectness Recognizes the langauge Does not recognize the languageFractional marks are possible.3. Marking scheme for Question 34 points 2 point 0 pointsNormalized GNFA normalized Not normalizedWork shown Work shown in each step Some of the work shown No work shownFinal RE Correctly read off GNFA Somewhat correctly read Incorrectly readCorrectness Specifies the langauge Does not specify languageFractional marks are possible.4. Marking scheme for Question 4Q4a : 1 mark for each RE for correctness, 1 mark for REs being differentQ4b : 1 mark for each NFA for correctness, 1 mark for NFAs being differentQ4c : 1 mark for each DFA for correctness, 2 marks for DFAs being different5. Marking scheme for each part of Question 52 points 1 point 0 pointsTechnique Correct proof technique Partially correct technique Incorret or no proofArgument Proof follows logically Proof has a few gaps Major gaps or no proofNeatness Easy to read Hard to read or no proof3CSCI3136: Assignment 2Summer 2021Student Name Login ID Student Number Student SignatureMarkQuestion 1 /10Question 2 /10Question 3 /10Question 4 /10Question 5 /10Total /50Comments:Assignments are due by 9:00am on the due date before class and should include this coverpage. Assignment must be submitted electronically via Brightspace. Please submit a PDF.You can do your work on paper and then scan in and submit the assignment.Plagiarism in assignment answers will not be tolerated. By submitting their answers tothis assignment, the authors named above declare that its content is their original work andthat they did not use any sources for its preparation other than the class notes, the textbook,and ones explicitly acknowledged in the Answers. Any suspected act of plagiarism will bereported to the Facultys Academic Integrity Officer and possibly to the Senate DisciplineCommittee. The penalty for academic Dishonesty may range from failing the course to expulsionfrom the university, in accordance with Dalhousie Universitys regulations regardingacademic integrity.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
