CSE 318 (Automata Theory and Formal Grammars)

Fall 2010

When and where	Mon, Wed, & Fri. 10:10 am - 11:00 am, Room XS 204
Instructor	Héctor Muñoz-Avila, munoz@cse.lehigh.edu
Instructor's office hours	Mon, 3:00PM-4:00PM Room 252 Packard Lab

Texts

Required:

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

Announcements

** Homework for Friday (19.Nov):

• Proof that if a language L is Turing-recognizable then L is enumerable with an enumerator Turing machine (hint: modify the enumerator we constructed in class by replacing the call to a decider with a call to a recognizer and take steps to ensure the enumerator will not get stuck in an infinite loop when it is calling the recognizer)
• 4.10 (hint: use the result of Problem 2.18 (a)), 4.12, 4.15

** Homework for Friday (12.Nov): 3.9, 3.14

** Homework for Friday (5.Nov):

• Construct an state diagram for a Turing machine deciding the language {(01)^n | n is greater or equal to 0}
• 3.15 (b), (d)
• 3.16 (b), (c)
• 3.8 (b)

** Homework for Friday (22.Oct): 2.30 (a), 2.30 (d), 2.31, 2.17, 2.25

** Homework for Friday (15.Oct): 2.4 (b), 2.4 (c), 2.6 (b), 2.12, 2.16, 2.26

** Homework for Friday (1.Oct): Construct a PDA for each of the following languages (the alphabet is {0, 1}):

• The language consisting of all words that start and end with the same character
• The language consisting of all palindrome words
• The language consisting of all words that have odd lenght and such that in the middle of the word they contain the character "0"

** Homework for Friday (24.Sept): 1.19 (b), 1.28 (b), 1.40(b), 1.21(b), 1.46 (c), 1.46 (d)

** Homework for Friday (17.Sept):

• Solve the following exercises: 1.16 b, 1.20 b, 1.20 d, 1.20 e, 1.20 g, 1.31
• prove the following statement: if L is a regular language then prefix(L) is regular. Where Prefix(L) is defined as follows:

  Prefix(L) = { x | x is an string and there exists an string y such that xy is in L}

  So for example if 0111 is in L then e, 0, 01, 011, and 0111 are all in Prefix(L).

** Homework due Sept. 10: 1.6 c, 1.6 f, 1.6 i, 1.7 b, 1.7 c, 1.7 g, 1.36

** Homework due Sept. 3: 0.1 (c), 0.1 (e), 0.2 (d), 0.2 (e), 0.2 (f), 0.3 (c), 0.3 (d), 0.3 (e), 0.3 (f), 0.4, 0.5, 0.11

Topics covered so far

• Math Background (Chapter 0)
• Deterministic Finite Automata (Section 1.1)
• Nondeterministic Finite Automata (Section 1.2)
• Regular Expressions (Section 1.3)
• Nonregular languages (Section 1.4)

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: Tue. Sep. 21 14:17:57 EDT 2010