Assignment 2
Instructor: Alex Brodsky
Due: 9:00am, Monday, May 28, 2021
- 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}. - [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. - [10 marks] Derive the regular expression that specifies the language recognzied by this NFA.
1
CSCI3136 Summer 2021 Assignment 2 - 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. - 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 - Marking scheme for each part of Question 1.
- 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 - Marking scheme for Question 2.
- 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. - Marking scheme for Question 3
- 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. - 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 - Marking scheme for each part of Question 5
- 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.