BBM 401 - Automata Theory and Formal Languages (Fall 2017)

Lecture: Mo. 9:00-9:50 @D8, Thu. 9:00-10:50 @D8

---

Instructor:

Lale Özkahya ozkahya-at-cs.hacettepe.edu.tr 203 +90 312 780 7551

---

Preferred Prerequisite

Foundations of Computer Science , a free textbook written by A. Aho and J. Ullman

Grading

• 60% Midterm Exams
• 40% Final Exam

Resources

• Introduction to the Theory of Computation, by Michael Sipser, 2006.
• Introduction to Automata Theory, Languages, and Computation (3rd Edition) by John E. Hopfcroft, Rajeev Motwani, Jeffrey D. Ullman.
• Margaret Fleck and Sariel Har-Peled's automata and formal languages notes, 2008 (available online)
• Jeff Erickson's Algorithm Notes (available online)
• Course Notes for "CS15-251: Great Theoretical Ideas in Computer Science" at CMU (available online)

Similar Courses

• MIT Open Courseware: Automata, Computability, and Complexity
• CS121: Introduction to the Theory of Computation at Harvard Uni.
• Automata Theory at Stanford Uni. Online
• CS154: Automata and Complexity Theory at Berkeley Uni.
• 15-251: Great Theoretical Ideas in Computer Science at Carnegie Mellon Uni.
• CS373: Introduction to the Theory of Computation at Uni. of Illinois
• CS374: Algorithms and Models of Computation at Uni. of Illinois

Office Hours

Email to arrange an appointment and also use Piazza for quick course related questions. Please enroll by following the link https://piazza.com/hacettepe.edu.tr/fall2017/bbm401

---

Schedule (Tentative)

Date	Topic	Reading (Sipser, Jeff Erickson (JE), Margaret Fleck and Sariel Har-Peled (MFSH)) and Exercises
Sept 25-29	Strings, Languages and Regular Expressions slides	Reading: Chapter 0, JE1 Discussion: MFSH Exercises: Problem Set 0, Sipser, Chapter 0: 3-6,8,9
Oct 2-6	DFA's and Closure Properties slides	Reading: Chapter 1.1, JE2, MFSHa, MFSHb Discussion: MFSH Exercises: Problem Set 1, Sipser, Chapter 1: 1-6
Oct 9-13	Nondeterminism: NFA definitions, equivalence with DFAs slides	Reading: Chapter 1.2, JE3, MFSH Discussion: MFSHa, MFSHb Exercises: Problem Set 2, Sipser, Chapter 1: 7-45
Oct 16-20	Regular expressions equivalence with NFAs, DFAs, closure properties of regular languages slides	Reading: Chapter 1.3, JE4, MFSHa, MFSHb Discussion: MFSH Exercises from Chapter 1: 7-45
Oct 23-27	Review and the first midterm exam
Oct 30-Nov 3	Proving Non-regularity slides	Reading: Chapter 1.4, MFSH Discussion: MFSH5 Exercises from Chapter 1: 46-65
Nov 6-10	Introduction to Turing Machines slides	Reading: Chapter 3.1, JE5, MFSHa,MFSHb, Variants of Turing Machines Exercises from Chapter 3: 1,2
Nov 13-17	Decidable Languages and the Halting Problem slides	Reading: Chapter 4, JE6, MFSHa, MFSHb, MFSHc Exercises
Nov 20-24	Reducibility slides	Reading: Chapter 5, MFSHa, MFSHb Exercises:
Nov 27 - Dec 1	Review and the second midterm exam
Dec 4-8	Context-free Grammars slides	Reading: Chapter 2.1, JE7, MFSH Exercises:
Dec 11-15	Normal Forms of Grammars slides	Reading: Chapter 2.1, MFSH Exercises:
Dec 18-22	Pushdown Automata and CFG's slides	Reading: Chapter 2.2, MFSH Exercises:
Dec 25-29	Non-Context-free Languages slides	Reading: Chapter 2.3 Exercises:

---

© 2017 Hacettepe University