辅导CSCI 3136、讲解Programming、c/c++程序设计辅导、Java，Python讲解
讲解R语言编程|讲解SPSS
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 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.
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 parenthesized.
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 Dominoes.
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. 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 alternatively,
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