Assignment 2
CSCI 3136: Principles of Programming Languages
Due February 3, 2020
Assignments are due on the due date by 23:59 AST and have to include this cover page. 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 Aca- demic 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.
Consider the following four languages:
DNA: The language of all DNA sequences (strings over the alphabet {A, C, G, T}) that do not contain any 4-letter string AGGT or AGTT or contain at least two disjoint substrings AxC, where x can be any character.
The following two strings are in the language: ACGAGCTTAGTC, because it does not contain AGGT nor AGTT; and AACGAGGTTTAGAGCTTAG, because it does contain the two substrings AAC and AGC (so it does not matter that it also contains the substring AGGT).
The following string is not in the language because it contains the substring AGGT but contains only one substring AxC: AACGAGGTTTAGAAGGCTTAG.
Nested parentheses: The language of properly parenthesized binary strings—that is, strings over the alphabet {0, 1, (, )}—whose nesting depth is at most 3.
A string σ is properly parenthesized if it can be defined inductively as follows:
• A string containing no parentheses—that is, a string formed only using the binary digits 0
and 1—is properly parenthesized. Such a string has nesting depth 0.
• A string (σ) (parenthesis, σ, parenthesis) is properly parenthesized if (but not only if) σ is properly parenthesized. Such a string has nesting depth one greater than the nesting depth of σ.
• The concatenation σ1σ2 of two properly parenthesized strings σ1 and σ2 is properly paren- thesized. The nesting depth of σ1σ2 is the maximum nesting depth of σ1 and σ2.
• Any string that cannot be constructed inductively using these three rules is not properly parenthesized.
The following string is in the language: 010011(101)(0(111)101((101)())), because the substring of parentheses ()(()(()())) is properly nested and has nesting depth 3.
The following two strings are not in the language: 1001(10))1001(), because ())() is not a properly nested sequence of parentheses; (11(101)(10(001(001)))01001), because the substring (()((()))) has nesting depth 4.
Dominoes: The language of all valid domino sequences. For the sake of keeping things simple, we only consider dominoes , , , , , , , , . A sequence of domino pieces is valid if for every pair of consecutive domino pieces, the right number of the first piece is the same as the left number of the second piece.
So the sequence is valid. The sequence is not.
Multiples: The language of all binary strings representing numbers that are divisible by 3 or 5. (A number divisible by 15 would also be in the language because it is divisible both by 3 and by 5.)
The strings 1011111 (95, divisible by 5), 110100111 (423, divisible by 3), and 11110 (30, divisible by both 3 and 5) are all valid.
The string 100101 (37) is not.
1
Question 1 (10 marks) Provide regular expressions that define the languages DNA and Nested parentheses. You may use “.” to match any character and character class syntax ([…]) to indicate different options for the same character (e.g., [AG] to match either A or G). Do not use any other extensions beyond the basic regular expression syntax (no repetition constructs other than *, no back references, etc.)
Question 2 (10 marks) Provide DFA that decide the two languages Nested parentheses and Domi- noes. Provide these DFA in graphical form. You are allowed to label transitions that match any charac- ter with “.” and transitions that match a range of characters using character class syntax. If a number of a domino does not matter, say you want to take the same transition for dominoes , , and
, you can simply write . The DFA you construct should be simple (i.e., should have only few states). If you end up constructing a DFA with 10 or more states, try to come up with simpler ones.
Question 3 (10 marks, bonus) Provide DFA that decide the two languages DNA and Multiples. Provide these DFA in graphical form. You are allowed to label transitions that match any character with “.” and transitions that match a range of characters using character class syntax. This question is bonus because the DFA are more complicated. My solutions for DNA and Multiples have 21 and 16 states, respectively. The 16 is best possible. I didn’t think too hard whether a DFA for DNA with fewer than 21 states exists.
Hint: For the Multiples language, your DFA should essentially do arithmetic modulo 15 (or al- ternatively, simultaneously do arithmetic modulo 3 and modulo 5). The 21 states for DNA are less daunting than they seem. There are a number of repetitions of the same sub-DFA that look for the forbidden patterns AGGT and AGTT and the compensating desirable pattern AxC.
?
2