CmpE 585 Special Topics In CmpE: Theory of Sequential Machines

Fall Semester 2009  

Announcements

· Here are the lecture notes for week three. (Scribe: Özkucur)

· You can find the lecture notes of the first two weeks here. (Scribes: Gökçe and Kurt.)

· Note that the subject matter of this course is ENTIRELY DIFFERENT than the previous incarnations of CmpE585!

· New announcements will be added to the top as they arrive. Please follow this announcements page frequently.

---

Subject:	Regular languages. State complexity. The Myhill-Nerode Theorem. Two-way accepters. Probabilistic finite automata. Quantum finite automata. Probability amplification in finite automata
References:	Sequential machines: Selected papers, Ed: E.F. Moore, Addison-Wesley, 1964. Introduction to Probabilistic Automata, A. Paz, Academic Press, 1971. Quantum Computing, J. Gruska, McGraw-Hill, 1999.
Instructor:	Cem Say

Prerequisite:

CmpE 350 or equivalent (Talk to the instructor if you have problems in this regard.)

Topics:

1. The Myhill-Nerode Theorem

2. Two-way accepters

3. Probabilistic Automata

5. Quantum Finite Automata

Exams:

Yes

Computer Usage:

None

Laboratory projects:

None.

Mathematics:

A lot of proofs and hard work.