EECS2001B Problem Set No. 3 Nov. 2020
Lassonde Faculty of Engineering
EECS EECS2001B. Problem Set No3 Posted: Nov. 18, 2020
Due: Dec. 8, 2020, by 4:00pm; in eClass.
Q: How do I submit? A:
(1) The text of all answers is expected to be typed.
(2) Submission must be ONLY ONE file
(3) Accepted File Types: PDF, RTF, MS WORD,
ZIP
(4) Deadline is strict, electronically limited.
(5) MAXIMUM file size = 10MB
It is worth remembering (quoted from the course outline):
The answers must be typed (but you may draw symbols by hand, if
it is easier for you).
The homework must be each individual’s own work. While consultations
with the instructor, tutor, and among students, are part of the learning
process and are encouraged, nevertheless, at the end of all this consultation each student will have to produce an individual report rather than a copy
(full or partial) of somebody else’s report.
The concept of “late assignments” does not exist in this course. Page 1 G. Tourlakis
EECS2001B Problem Set No. 3 Nov. 2020
1. (5 MARKS) Design a regular expression α over {0, 1} that defines the language over {0, 1} of all the strings of Odd length.
Clearly justify why your regular expression works as stated (NOT by example; give a “general argument” or a “proof” if you prefer (although a proof is not required in this problem)).
2. (5 MARKS) Build an NFA that accepts precisely all the strings over {0, 1} of length ≥ 2 that contain at least one 1 among their last 2 symbols.
You must argue that your design is correct. Again, NOT by example.
3. (5 MARKS) Convert to NFA (both over {0, 1}) without comment:
• 01(0+1)∗10 • (0+1)+101
4. (4 MARKS) Convert without comments each of the immediately previ- ous two NFA (problem #3) to a FA.
5. (5 MARKS) Prove that the following is not a regular language: Over {0, 1}: The set {0n102n : n ≥ 0}
Page 2 G. Tourlakis