CSE 318 (Automata Theory and Formal Grammars)

Fall 2009

When and where	Mon, Wed, & 2:10 pm - 3:00 pm, Room Christmas Saucon 203
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

Announcements will be made here.

4.6, 4.7, 4.12

Past Homeworks

Describe a way to encode PDAs.
Exemplify your encoding with the PDA of Figure 2.15
Prove that the class of all encodings of PDAs is decidable
4.3, 4.15, 4.10

Construct the state diagram for a enumerator Turing machine that prints all binary numbers in lexicographical order.
Prove that the class of languages that can be enumerated by enumerator Turing machines is closed under intersection
Prove that the class of languages that can be enumerated by enumerator Turing machines is closed under concatenation

Construct a state diagram for the Turing machine that decides the palindrome binary numbers.
3.9, 3.15 (c), 3.15 (d), 3.16 (b), 3.16 (d)

Convert the CFG G3 from Example 2.3 (Page 103) into a PDA P using the procedure of Lemma 2.21. Analize the resulting P and explain why it recognizes the same language that G3 generates.
Convert the PDA M1 shown in Figure 2.15 (Page 113; assume that only q4 is favorable and hence M1 does not recognize the empty word as being of the form 0^n 1^n) into an equivalent CFG G using the procedure outlined in Lemma 2.27. Analize the resulting G and explain why it generates the same language that M1 recognizes
2.30(a), 2.31

Construct pushdown automata for the languages indicated in exercises 2.4(d) and 2.6(c)
2.20 (assume Theorem 2.20 to be true; Basically what you have to do is figure out how to construct a pushdown automaton for A/B assuming you are given a pushdown automaton for A and a finite automaton for B)
2.25 (again assume Theorem 2.20 to be true; Basically what you have to do is figure out how to construct a pushdown automaton for suffix(A) assuming you are given a pushdown automaton for A)

2.4(b), 2.4 (e), 2.16, 2.17, 2.26

1.21(b), 1.46(a), 1.46(c), 1.47
Try to prove the impossible: that the language 0*1* is not regular. Explain where the proof fails when trying to use the pumping lemma on the string string 0^p 1^p.

Homework (Friday Sept. 11): 1.16(b), 1.13, 1.7(e), 1.20(d), 1.20(e), 1.20(g), 1.19(a), 1.31, 1.43

Homework (Friday Sept. 4): 1.14, 1.4 (c), 1.4 (f), 1.5 (c), 1.6 (d), 1.6 (i)

Homework (Friday August 28): 0.1 (d), 0.1 (e), 0.2 (c), 0.2 (d), 0.2 (e), 0.3 (f), 0.5, 0.11

Topics covered so far

Introduction (Math background assumed to be known; check Chapter 0)
Finite automata (Chapter 1)
regular expressions
Non-regular languages
Context-free grammars (Chapter 2)
Pushdown automata
non context-free languages
Turing machines (Chapter 3)
variants of Turing machines
Enumerator Turing machines
Church-Turing Thesis
Decidable languages (Chapter 4)
Non decidable languages

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. Aug. 24 13:17:57 EDT 2009