$30
COMP 330A Assignment 1
—————————————————————————————————————————————————————
—————————————————————————————————————————————————————
—————————————————————————————————————————————————————
—————————————————————————————————————————————————————
In question 1.20 below please provide strings of size at least 7. If no such string exists, just say "none of size ≥7" and give
examples of any size.
[8%]
[16%]
[12%]
[14%]
—————————————————————————————————————————————————————
————————————————————————————————————————————————————
————————————————————————————————————————————————————
1.98 Consider the (binary) language L={ w | 010 or 101 is a substring of w}.
a) Draw a DFA that recognizes exactly the regular language L.
b) Prove by mathematical induction that the DFA you provided in a) recognizes
exactly the language L.
[8%]
[10%]
[8%]
[12%]
NFA to an equivalent DFA.
Please notice the instance below is NOT the same as in the book…
MYHILL-NERODE
THEOREM
1.99 Consider the following regular languages over binary alphabet {0,1}
L1 ={ number w is a multiple of 3},
L2 ={ w=w1w2…wn is a multiple of 3}
L3 ={ w=wnwn-1…w1 is a multiple of 3}.
a) Identify manually which of these numbers are multiples of 3:
(Each line is a single number. I broke it down in blocks of 6 bits for readability.)
1) 101010 101011 010100 111010 110110 110101 010101 101111 101101
2) 111111 111111 111111 111011 110111 101111 110111 111110 111111
3) 100001 000000 100000 000001 000000 000010 000000 100000 010101
4) 110011 001100 110011 001100 110011 001100 110011 001100 110011
b) Prove that L1 = L2 = L3.
c) Explain the link with the automaton seen in class:
n
∑
k=1
(−1)
kwk
n
∑
k=1
(−1)
kwk
[12%]
M3,2
1
0
q0
q1
q2
0
0 1
1