COMP 360 - Fall 2020- Assignment] Due: 11:59pm Sept 24 th

COMP 360 - Fall 2020- Assignment^]

Due: 11:59pm Sept 24 th.

General rules: In solving these questions you may consult books or other available notes, but you need to provide citations in that case. You can discuss high level ideas with each other, but each student must find and write her/his own solution. Copying solutions from any source, com-

pletely or partially, allowing others to copy your work, will not be tolerated, and will be reported to the disciplinary o ce.

You should upload the pdf file (either typed, or a clear and readable scan) of your solution to mycourses.

1. What are the languages L(M) and L(N) ?
2. Following the approach that was used in Lecture 3, design a DFA that recognizes L(M) [ L(N). (It su   ces to draw the state diagram).
3. Design a smaller DFA that recognizes L(M) [ L(N).

3. (20 points) For each one of the following languages over the alphabet ? = {0,1} give a DFA that recognizes them. (It su ces to draw the state diagram).
   1. The set of all strings x such that the number of ones in x is divisible by 3 and not divisible by 2 (for example 1011 is accepted but 10 and 111111 are not in the language).
   2. of length at least two that start and end with the same symbol (for example 00, 1011 are accepted but 0, 011011 and 10 are not accepted).
   3. The set of all the strings that contain all of the four strings “00”, “01”, “10”, and “11” as substrings. (for example 101100 is accepted).
   4. The set of all strings of length at least three such that every three consecutive symbols contain at least two 1’s (for example 1101 is accepted but 1010111 is not).
4. (10 points) Let L be a language over {0,1} consisting of a single word of length k. Describe a DFA with k + 1 states that accepts L. Prove that no DFA with fewer than k + 1 can recognize such a language.
5. (10 points) Let L be a finite language over {0,1}, and let k be the length of the longest word in

L. Describe a DFA with 2^k+1 states that accepts L.

6. (10 points) Give an NFA M = (Q,?, ,q₀,F) accepting the following language over the alphabet {a,b,c,d}: The set of all strings that contain at least two a’s with no c appearing between them (For example bcabbdaca and aa are accepted but abccdabcb and bd are not accepted). Drawing the state diagram su ces.
7. Let M be a DFA accepting a language A over the alphabet {0,1}. For each one of the following languages design an NFA (based on M) that accepts the language.
   1. (5 points) A \ {"}.
   2. (10 points) {w^R|w 2 A}, where w^R is the reverse of the string w. (For example the reverse of 01101 is 10110).
8. (15 points) Let r,s and t be regular expressions. Prove or disprove each one of the following equalities.
   1. (rs [ r)? = r(sr [ r)?
   2. s(rs [ s)? = rr?s(rr?s)?
   3. (r [ s)? = r^?[ s?