代做CSCI3136编程代写、Java，Python，CSS程序代写

日期：2021-05-23 10:51

Assignment 2

Instructor: Alex Brodsky

Due: 9:00am, Monday, May 28, 2021

1. 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 the

transition function for the DFA.

3. [10 marks] Derive the regular expression that specifies the language recognzied by this NFA.

1

CSCI3136 Summer 2021 Assignment 2

4. 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 set

of all strings over the alphabet Σ = {x} whose length is divisible by 3. Note: please do

not 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 regular

expression

(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 are

regular:

(a) [5 marks] The language Lnot3 of all strings over alphabet Σ = {x} that are not

divisible by 3.

(b) [5 marks] The language L = LQLeven where LQ = {a

p?1

| p ∈ PRIME} and Leven =

{(aa)?}. 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.

2

CSCI3136 Summer 2021 Assignment 2

Marking Scheme

1. Marking scheme for each part of Question 1.

2 points 1 point 0 points

States Correct # of states 1 or 2 states missing Incorrect

Transitions Correct Somewhat correct Incorrect

Correctness Recognizes the langauge Does not recognize the language

2. Marking scheme for Question 2.

4 points 2 point 0 points

States Correct # of states 1 or 2 states missing Incorrect

Transitions Correct Somewhat correct Incorrect

Correctness Recognizes the langauge Does not recognize the language

Fractional marks are possible.

3. Marking scheme for Question 3

4 points 2 point 0 points

Normalized GNFA normalized Not normalized

Work shown Work shown in each step Some of the work shown No work shown

Final RE Correctly read off GNFA Somewhat correctly read Incorrectly read

Correctness Specifies the langauge Does not specify language

Fractional marks are possible.

4. Marking scheme for Question 4

Q4a : 1 mark for each RE for correctness, 1 mark for REs being different

Q4b : 1 mark for each NFA for correctness, 1 mark for NFAs being different

Q4c : 1 mark for each DFA for correctness, 2 marks for DFAs being different

5. Marking scheme for each part of Question 5

2 points 1 point 0 points

Technique Correct proof technique Partially correct technique Incorret or no proof

Argument Proof follows logically Proof has a few gaps Major gaps or no proof

Neatness Easy to read Hard to read or no proof

3

CSCI3136: Assignment 2

Summer 2021

Student Name Login ID Student Number Student Signature

Mark

Question 1 /10

Question 2 /10

Question 3 /10

Question 4 /10

Question 5 /10

Total /50

Comments:

Assignments are due by 9:00am on the due date before class and should include this cover

page. 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 to

this assignment, the authors named above declare 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 and possibly to the Senate Discipline

Committee. The penalty for academic dishonesty may range from failing the course to expulsion

from the university, in accordance with Dalhousie University’s regulations regarding

academic integrity.