CSE 318 (Automata and Formal Grammars)

Fall 2007

When and where	Mon, Wed, & 2:10 pm - 3:00 pm, Room MG 290
Instructor	Héctor Muñoz-Avila, munoz@cse.lehigh.edu
Instructor's office hours	Mon, 4:00PM-5:00PM, Room 252 Packard Lab

Texts

Required:

Michael Sipser Introduction to the Theory of Computation (Second Edition)

Announcements

** FINAL GRADES are here

** Includes all corrections you sent per e-mail

** You are welcomed to see the final exam on Monday Dec. 17 from 3pm-4pm or on the week before the beginning of the Spring Semester 2008

** Maximum score for the final exam is 60/60

Topics covered so far

• Introduction
• Math background (no slides; covered Chapter 0)
• Finite Automata (Covered Section 1.1 until the subsection "Regular Operations")
• Nondeterministic Finite Automata (Covered Section 1.2 until the subsection about equivalence between NFAs and DFAs)
• NFAs vs DFAs (Covered Section 1.2 until "Clousure under regular operations")
• Clousure properties for regular languages (Covered Subsection "Clousure under regular operations" in 1.2)
• Regular expressions (Section 1.3)
• Nonregular Languages (Section 1.4)
• Context-free Languages (Section 2.1)
• Pushdown Automata (Section 2.2)
• Equivalence of Pushdown Automata and Context-Free Grammars (Section 2.2)
• Non Context-Free Languages (Section 2.3)
• Turing machines (Section 3.1)
• Multi-tape, Multi-head, Non-deterministic Turing machines, Enumerators (Section 3.2)
• Equivalence between Turing machine variants (Section 3.2)
• Enumerability (Section 3.2, 3.3, and Section 4.2)
• Decidability (Section 4.1)
• Undecidability (Chapter 4.2)

Communication

All announcements, handouts, etc. will be posted in this web site:

www.cse.lehigh.edu/~munoz/CSE318

Homework and Quiz

There will be quizzes and written homework assignments.  Students may turn in the homework in my mailbox before the class begins but will loose 7% of their homework grade.

Attendance

Attendance to classes is required. Although I don't take list,  pop quizes will not be announced. Failure to present a pop quiz will result in 0 points. Participation in class and attendance will add points to the "Quiz+Homework" grade.

Exams

There will be two tests and a final exam.

Exams will not be repeated. Unless an extreme situation occur, failure to present a test will result in 0 points. If an extreme situation does occur causing a person not to present an exam, the average of the score in the other two exams will be assigned as score for the missing exam.

Cheating

You're responsible for doing your own work on all assignments and exams. Copying other people's work is cheating, and if I catch you doing it I'll report it to the honors council.

Grading

Exams:                    80% (Test # 1: 20%, Test # 2: 20%, Final Exam: 40%)
Quiz+Homework:   20%
 

Last update: Mon. Nov. 28 12:17:57 EDT 2007