Course Structure

Lectures = 2 [HEC recommended 3]        Labs = 0        Credit hours = 3

Prerequisites

Course in Discrete Mathematics or equivalent, fluency in mathematical expression, and some programming experience.

The implicit requirement of this course is that you have a general knowledge of mathematical and discrete structures. This includes but is not limited to graphs, trees, inductive proofs, relations and functions, etc. Some of this will be reviewed during the first week of classes.

Course Objectives

The course aims to develop an appreciation of the theoretical foundations of computer science through study of mathematical and abstract models of computers and the theory of formal languages. Theory of formal languages and use of various abstract machines as 'recognizers' and parsing will be studied for identifying the synthetic characteristics of programming languages. Some of the abstract machines shall also study as 'Transducers'.

Course Outline (Based upon HEC Curriculum of CS, Revised 2009)

Finite State Models: Language definitions, Regular expressions, and Regular languages. Finite automata (FAs), Transition graphs. Nondeterministic finite automata (NFAs), Kleene's theorem, Transducers, Pumping lemma and non regular languages. Grammars: Context-free grammars, Derivations, derivation trees, and ambiguity, Simplifying CFLs, Normal form grammars and parsing, Decidability, Chomsky's hierarchy of grammars. Turing Machines Theory: Turing machines, Post machine, Variations on Turing machines, Turing machine encoding, Universal Turing Machine, Context sensitive grammars, defining computers by Turing machines.

Class Time

Mondays, 10:00 AM - 11:30 AM and Fridays, 8:30 AM - 10:00 AM

Office Hours

Mondays: 11:30 AM - Noon;    Wednesdays: 10:00 AM - 10:30 AM;    Fridays: 11:30 AM - Noon and 7:00 PM -??:?? PM.

Homework

There will be approximately 3-4 homework assignments during the semester, and will involve solving problems. In general, you will have adequate time to complete each assignment. However, you should begin working on each assignment early so that you will have plenty of time to do properly. Waiting to start working until the night before the assignment is due is a bad idea. Late homework will be accepted with a penalty of 50% per calendar day. Note that after the class submission means “Late homework”.

Exams

Midterms and final exam will be given that examines the student’s knowledge of the course material. The final exam is comprehensive. No study guide(s) will be given before exams.

Pop Quizzes

The date of the quiz will NOT be announced (there will be surprise quizzes.) A quiz is held during the first 10 minutes of the class. Late students will not be given extra time to complete the quiz. No late quizzes will be accepted; no make-up quizzes.

Make-up and Late Policy

There is no make-up date for missed homework, quizzes, or exams. Missed work will result in grade of 0 for the applicable homework, quiz, or exam. Exceptional circumstances should be discussed with me in advance. Make-ups of exams for this class will only be given in the case of documented and valid circumstances.

Attendance and Class Participation

Participation in the classroom activities is very important to the learning process. During class, I expect my students to be dutiful and to pay attention. Do not be disruptive to the teacher or to the other students. If you are late or must leave early, do so without disturbing the class. Please turn off cell phones and beepers. I reserve the right to remove any disruptive students from MY class.
Let me repeat myself a little bit differently. Students are expected to attend each and every lecture. Attendance and active participation during a lecture will help you learn the material and succeed in class. Missed lecture/material will influence your understanding of material covered later in class. Any missed material due to absences is the responsibility of the student.
Your overall in-class attitude has no bearing on your grade. I will not penalize students who look bored, angry, or frustrated, nor will I give extra points to students who are excited or thrilled to be in my class. Allow your face to show your honest emotions about the class; it will not be taken personally. You will be graded solely on the work you turn in.

Texts

Our Primary Source

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.

Our Secondary Source

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addion-Wesley, 2006.

HEC Recommended Text Books/Reference Books:

S. P. Eugene and Kavier, Theory of Automata, Formal Languages and Computation, New Age Publishers, 2005.

P. Linz, An Introduction to Formal Languages and Automata , Jones and Bartlett Publishers, 2006.

John Hopcroft and Jefferry Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001.

John C. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill , 2002.

Ethics

The Honor Code will be strictly enforced in the classroom. It is a violation to represent joint work as your own or to let others use your work; always acknowledge any assistance you received in preparing work that bears your name. You are expected to work independently unless explicitly permitted to collaborate on a particular assignment. It is not a violation to discuss approaches to problems with others; however, it is a violation to use wording or expressions in your assignments that have been written by others without acknowledging the source.

Class Schedule

Lectures Notes

You are expected to study all the material in each chapter covered in the class even if that material is not explicitly discussed in class. The lecture notes are a supplement to the course textbooks. These lecture notes are supposed to help you understand the textbook material better; they are a replacement for neither the textbook nor the lecture itself.

Automata Theory Lecture Notes     [Always Updating!]

Points Distribution

Homeworks

Exams

Grades

Students with Disabilities

If you have a documented disability and require accommodations to obtain equal access to my instructions and/or lectures, please contact me (during my office hours) to make arrangements for necessary classroom adjustments.

You can do it if you try!

If you wish to succeed in this course
If you wish to do better
If you wish to fail in this course