CSCI3136
Assignment 1
Instructor: Alex Brodsky
Due: 9:00am, Friday, May 21, 2021
1. [5 marks] Suppose you were modifying the Java compiler to include a new encrypted
keyword that causes Java to store the contents of the specified variable in encrypted form.
E.g.,
encrypted String password = “hello”;
would cause the contents of password to be encrypted.
Which of the phases of the Java compiler would need to be modified and why
2. For each of the following languages give the regular expression that matches the strings in
the language. Note: You can use . to denote “any” character in the alphabet.
(a) [5 marks] The language, over the English alphabet, of strings that begin and end with
vowels (assume ’y’ is a vowel).
(b) [5 marks] The language of strings, over alphabet Σ = {x, y, z}, whose length is divisible
by 5. E.g., xyzyx.
(c) [5 marks] The language, over the alphabet of decimal digits, of strings that represent
integers divisible by 200. E.g., 13400.
(d) [5 marks] The language of strings over the alphabet Σ = {a, b, c} that do not contain
the substring ac. E.g., abcab.
3. For each of the following languages, give a DFA (graphical representation) that recognizes
the language.
(a) [5 marks] The language of all strings over the alphabet Σ = {x, y, z} that end in either
xx or yy. E.g., xyzyxzxx.
(b) [5 marks] The language of words over the alphabet Σ = {a}, whose length is not
divisible by 4. E.g., aaa.
(c) [5 marks] The language, of trinary strings (Σ = {0, 1, 2}) such that the sum of the
digits is divisible by 3. E.g., 012102.
1
CSCI3136 Summer 2021 Assignment 1
Marking Scheme
1. Marking scheme for Question 1.
2 points 1 point 0 points
Correctness All phases correctly identified Some phases correctly identified No phases are identified
3 points 2 points 0 – 1 points
Justification Good just. for each phase Some just. for each phase Poor or no just. for each phase
2. Marking scheme for each part of Question 2.
2 points 1 point 0 points
Approach Approach is workable Approach is not workable
4 points 2 point 0 points
Correctness Handles all cases Misses some cases Misses most cases
Fractional marks are possible.
3. Marking scheme for each part of Question 3.
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
Fractional marks are possible.
2
CSCI3136: Assignment 1
Summer 2021
Student Name Login ID Student Number Student Signature
Mark
Question 1 /5
Question 2 /20
Question 3 /15
Total /40
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 ex-
pulsion from the university, in accordance with Dalhousie University’s regulations regarding
academic integrity.
