编译器代写: Assignment 2 CSCI 3136

Banner ID: Banner ID: Banner ID:

Name: Name: Name:

Question 1 Question 2

Total

Assignments are due on the due date before class 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.

Question 1 (30 marks) Do the following for both of the following languages 􏱎 of binary strings: • Provide a regular expression R such that 􏱎 = 􏱎 (R).
• Translate the regular expression into an NFA N such that 􏱎 = 􏱎 (N ).
• Translate the NFA into a DFA D such that 􏱎 = 􏱎 (D).

• Translate the DFA into a minimized DFA D′ such that 􏱎 = 􏱎 (D′).

Your regular expression may use the wildcard . to denote any character but must not use any other extensions of plain regular expression syntax such as +, ? or {m,n}. You may simply state the regular expression and provide the NFA and the two DFA in graphical or tabular form without stating how you obtained them. However, it is not sufficient that these automata decide the correct languages. They must be the automata you obtain by applying the procedures described in class for transforming regular expressions into NFA, NFA into DFA, and DFA into minimized DFA.

1. (a)  All binary strings that contain two 1s separated by one or two characters. For example, the strings 01010100 and 00111100001 belong to this language because the underlined substrings start and end with a 1 and have length 3 and 4, respectively. The string 00110001100 does not belong to this language because every substring that starts and ends with a 1 has length less than 3 or greater than 4.
2. (b)  All binary strings where every pair of consecutive 1s is immediately preceded by at least two 0s. For example, the string 0011010001101 belongs to this language because, as the underlined substrings show, each pair of consecutive 1s is preceded by two or more 0s. The strings 00101101 and 001100011101 do not belong to this language because both contain a pair of consecutive ones where the two immediately preceding characters include another 1.

Question 2 (10 marks) Use the Pumping Lemma to prove that both of the following languages of binary strings are not regular:

1. (a)  The language of all binary strings with the same number of 0s and 1s. For example, 00101011 belongs to this language while 111100 and 0010110 do not.
2. (b)  The language of all binary strings whose lengths are powers of 2, that is, every string σ in this language satisfies |σ| = 2n, for some integer n ≥ 0.