Assignment 1 (Due 24 Feb at end of class)

General Rules:

a. Please hand in only your own work.
b. Grades discounted 10% per day late.

Tasks

1) For the relation: { (a,b), (b,c), (c,d),(e,d) } please compute:
a) The transitive closure
b) the reflexive and transitive closure
c) symmetric closure.
2) Provide a language which has the following property:
a) L* = empty set
b) L+ contains the empty string
c) L* contains the strings "0" and "1"
d) The length of every string in L* is an even number.
3) Give DFAs for the languages that are:
a) The set of all strings (over 0,1) that do not contain a substring "000".
b) The set of all strings (over 0,1) such that every 3 char substring contains a 0.
4) State the language of a machine M (over 0,1) with a transition function:
a) (q0,0) = q0, (q0,1) = q1, (q1,0) = q2, (q1,1) = q1. (q2.0) = q2, (q2,1) = q1, with F = {q0, q1}
b) (q0,0) = q1, (q0,1) = q2, (q1,0) = q3, (q1,1) = q0, (q2,0) = q0, (q2,1) = q3, (q3,0) = q3, (q3,1) = q3 with F = {q0}
5) Write an NFA which accepts strings where the 4th symbol from the right is "0". Use the method to create an equivalent DFA.