How would i do #4 from the assignment? I’m not sure how i would start.
CSC236H, Winter 2016
Assignment 5
Due April 8th, 11:59 p.m.
? You may work in groups of no more than two students, and you should produce a single solution in a
PDF ?le named a5.pdf, submitted to MarkUs. Submissions must be typed.
? Please refer to the course information sheet for the late submission policy.
1. For each of the following languages give a regular expression that accepts the language.
You do not need to prove that your regular expression is correct.
(a) L = {x ? {0, 1}? : x ends with 1 and does not contain the substring 00}.
(b) L = {x ? {0, 1}? : x = 0n 1m , where n + m is a multiple of 3}.
2. Determine the set of binary strings generated by the following regular expressions.
(a) 0? 1(0? 10? 1)? 0? .
(b) (1 + 01)? (0 + 01)? .
3. Give an NFA for each of the following languages.
(a) L1 = {s ? {a, b, d}? : s contains exactly one occurrence of the substring dab
and no occurrence of the substring bad}.
(b) L3 = {s ? {0, 1, 2}? : the integer value of s (in ternary notation) is one less than a multiple of 4}.
(For example, 21 ? L3 because the integer value of ?21? in base three is 2 ? 3 + 1 ? 1 = 7 = 8 ? 1.)
0
0
1
1
,
,
be the alphabet of all 2 ? 1 matrices consisting of elements from {0, 1}.
,
0
1
0
1
A string of symbols in ? gives two rows of 0?s and 1?s. Consider each row to be a natural number
written in binary, and let
4. Let ? =
L = {x ? ?? : the bottom row of x is smaller than the top row}
For example,
1
0
1
0
,
,
,
1
0
0
1
? L because 1010 > 1001, but
0
1
0
,
,
1
0
1
? L since
010 < 101.
Construct a DFA that accepts L. Your DFA must only have two states. One mark will be deducted
for each extra state that your DFA uses.
Provide an appropriate state invariant for your DFA. Do not use regular expressions in your state
invariant.
1
5. Let ? be an arbitrary alphabet.
For every language L ? ?? and symbol a ? ?, de?ne Quot(L, a) = {w ? ?? : wa ? L}.
For example, if ? = {0, 1}, a = 1 and L = {1, 110, 011}, then Quot(L, a) = { , 01}.
Prove that if L is regular then so is Quot(L, a). More speci?cally, you must show the construction
of a DFA for Quot(L, a) (where L ? ?? is an arbitrary regular language and a ? ?), and prove the
correctness of the DFA.
6. Suppose we know that the language
L = {0n 1n : n ? 0}
is not regular.
Use closure properties of regular languages to prove that the language {0i 1j : i, j ? 0, i = j} is not
regular.
2