Due Dates: Oral presentations of material begin on 30 August.

Written descriptions of material presented due one week after presentation.

**Topics:** Finite State Automata (Chapter 1).

An integral part of this class is understanding and presenting the problems
assigned as homework. Everyone is expected to do all the problems,
but we will take turns on who presents the problem solutions to the class
(every 2-3 weeks, depending on the number of students in the class). Within
a week of presenting a problem solution to the class, you must submit a written
description of it, via the Blackboard system. The written solutions
will be posted on the Blackboard website for the class, so, they can used
by everyone to study for the exams. Since it's hard to write
down answers that are concise and are easily readable by all, if you wish
to improve a grade on any problem, you may resubmit it for grading.

## Using Blackboard

To use the Blackboard system for this
course, you

**must be enrolled** in the course. A login name
and default password are generated for each CUNY student. If you have troubles accessing Blackboard, contact

Blackboard Support in the Information Technology Division. You can also visit the Help Desk in the Computer Center (first floor, Carman Hall) in person. They can reset passwords and help with simple Blackboard issues.

### Academic Integrity

Quizzes and assignments are open book and open notes, but you may not accept
help from others while taking your quiz. For assignments, you must acknowledge
all others (including books and websites) with whom you worked with or received
help. All work must be your own.

## Undergraduate Problems

All students enrolled should complete the following:

- Give a state diagram of a DFA that recognizes the following language:

{w | w begins with a 1 and ends with a 0}

(assume that the alphabet is {0,1}.)
- Give a state diagram of a DFA that recognizes the following language:

{w | w contains at least 3 1s}

(assume that the alphabet is {0,1}.)
- Give a state diagram of a DFA that recognizes the following language:

{w | w has length of 3 or more and starts with a 0}

(assume that the alphabet is {0,1}.)
- Give a state diagram of a DFA that recognizes the following language:

{w | w has even length}

(assume that the alphabet is {0,1}.)
- Given the formal description of DFA M is
({q
_{1}, q_{2}, q_{3}, q_{4}, q_{5}}, {u,d}, δ, q_{3}, {q_{3}})
where δ is:
| u | d |

q_{1} | q_{1} | q_{2} |

q_{2} | q_{1} | q_{3} |

q_{3} | q_{2} | q_{4} |

q_{4} | q_{3} | q_{5} |

q_{5} | q_{4} | q_{5} |

Give the state diagram of this machine.

## Graduate Problems

Students enrolled for graduate credit, should complete all the undergraduate problems, as well as:

- Give a state diagram of a DFA that recognizes the following language:

{w | w does not contain the substring 110}

(assume that the alphabet is {0,1}.)
- Give a state diagram of a DFA that recognizes the following language:

{w | w contains the substring 11 **or** the substring 00}

(assume that the alphabet is {0,1}.)
- Give a state diagram of a DFA that recognizes the following language:

{w | w contains the substring 11 **and** the substring 00}

(assume that the alphabet is {0,1}.)