#
代写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