博客

CSCI2115

Assignment 3

北美计算机作业代写 For this question use the automaton simulator shown in class, which is located at https://automatonsimulator.com/ to create NFAs to recognize···

1.ConstructNFAs that recognize the specified languages  北美计算机作业代写

For this question use the automaton simulator shown in class, which is located at https://automatonsimulator.com/ to create NFAs to recognize the following languages.

Use the save button to save the text representation of the DFAs in files called q1a.txt, q1b.txt, and q1c.txt. Submit these files as part of your submission. The marker will load your NFAs into the automaton simulator and test them. See the video on Brightspace in Lecture 4 or in the Tutorials section on how to use the automaton.  You should also submit a diagram of your NFA (in case the text files become corrupted).

a.[5marks] The language specified by 000 (101 | 010)* (011 | 110 | 111) where the alphabet is Σ = {0, 1}.

b.[5marks] The language specified by (x* y z*) | (y* z y*) | (z* x y*) where the alphabet is Σ = {x, y, z}.

c.[5marks] The language of all strings over Σ = {A, B} where the number of As is divisble by 3 or the number of Bs is divisible by

2.Prove a language is regular by construction.  北美计算机作业代写

For the following two questions, prove that thelanguages are regular by showing how they can be constructed using the operations from the definition of what a regular language  For example

Theorem 1 The language of all even-length strings over the alphabet Σ = {a} is regular.

Proof: Let L_a = {a} which is regular because this is a base case of the definition of a regular language.

Let L_aa = L_aL_a = {aa}, which is regular because the concatenation of two regular languages is regular, by definition.

Let  L  = L^∗aa,  which  is  also  regular  because  the  Kleene-*  of  a  regular  language  is also regular, by definition.

But, L is the set of all even-length strings over Σ. Hence, this completes the proof.

a.[5marks] The language L_not3 of all strings over alphabet Σ = {x} whose length is not divisible by 3.

b.[5 marks] The  language  L  =  L^∗P   where  L_P  =  {a^p  | p  ∈ PRIME } Note:  You  may recall from our lectures that the language of prime-length strings is not regular, yet rest assured that L is definitely regular. (This is the hardest question in this assignment.) Hint: You will need to use a very simple property of almost all prime numbers to prove this.

Marking Scheme 北美计算机作业代写

1.Markingscheme for each part of Question

2. Markingscheme for each part of Questions 2

Submission  北美计算机作业代写

Assignments are due by 9:00am on the due date before class. Assignment must be submitted electronically via Brightspace. Please submit a zip file containing the PDF and the three text files required in Question 1. It is strongly recommended that your also include diagrams of the NFAs in Question 1, in case the text files become corrupted. You can do most of your work on paper and then scan in and submit the assignment.

Please use an appropriate app to scan in your assignment instead of just taking a photograph of it. Photos of assignments tend to be hard to read and are much more error-prone for the marker.

Academic Integrity  北美计算机作业代写

Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the student named above declares that its content is their original work and that 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 be reported to the Faculty’s Academic Integrity Officer. The penalty for academic dishonesty may range from grade deduction to expulsion from the university, in accordance with Dalhousie University’s regulations regarding academic integrity.

更多代写：留学生CS代写 美国exam代考 美国stata代写  人类学essay代写 paper代写 留学生课业essay代写违法吗

合作平台：天才代写 幽灵代写  写手招聘  paper代写