CS 3240: Languages and Computation
Fall 2007
Tue, Thur 1:35 pm - 2:55 pm, CoC 101

---

Instructor: Alberto Apostolico (axa@cc) Office: KACB 1310 Phone: 404- 8942592 Office Hours: Tue., Thur. 4-5pm, or by appointment

TA: Akshay Wadia TA Email: awadia@gatech.edu TA Office:  KACB 2124 TA Office Hours: Tue., Thur. 10:30am-11:30am, or by appointment

---

[ Announcements | Course Description | Course Outline | Homework and Project Information | Class Schedule ]

Announcements (back to top)

Course Description (back to top)

One way to understand the fundamental structure, power and limitations of computation is through the study of decision problems associated with various classes of languages. A language is an aggregate of strings from some alphabet, and it can be characterized by giving a machine that discriminates or accepts those strings while rejecting all others. Alternatively, one can give a generative device or grammar capable of producing the strings in the language but none of the others. The objective of this course is to learn these abstract languages and the computations inherent to their corresponding machines and grammars. Scanners and parsers of compilers represent practical incarnations of these theories. The limits of computability, Turing machines, decidability, and  reducibility will also be discussed. The key objectives of this course are the following:

• in-depth understanding of computational powers of regular language, context-free languages, and Turing machines;
• understanding of some practical applications of regular and context-free languages;
• some problem solving by combining the two.

Course Outline (back to top)

Required Textbook

Introduction to Automata Theory, Languages, and Computation (3^rd Edition)
by John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman
Hardcover: 535 pages
Addison Wesley; 3 edition (July 8, 2006)
ISBN-10: 0321455363
ISBN-13: 978-0321455369

You must register at http://www.aw.com/gradiance using the student access code accompanying your copy of the textbook and the token you were shown in class

Outline

• Lexical analysis, scanners, pattern matching
• Regular expressions, DFAs, NFAs and automata
• Limits on regular expressions, pumping lemma
• Practical parsing, LL and LR parsing
• Context-free languages, grammars, Chomsky Hierarchy
• Pushdown automata, deterministic vs. non-deterministic
• Attribute grammars, type inferencing
• Context-free vs. context-sensitive grammars
• Turing machines, decidable vs. undecidable problems, reducibility

Grading

• Homework: 20%
• Mini-project: 25%
• Tests: 30 %
• Final: 25%

Homework and Project Information (back to top)

Collaboration Policy

You are allowed to discuss course materials, homework problems, and programming assignments in small groups, but limited to discussion of general ideas only. You must write your solutions completely independently, and must report the names of your collaborators with whom you discussed the assignments. Under no circumstances may you copy solutions from any source, including but not limited to other students solutions, official solutions distributed in past terms, and solutions from courses taught at other universities. Violation of these rules may result in disciplinary actions.

Homework Guideline

Homework answers should be concise, complete, and precise. All homework assignments are due at the beginning of the class. All programming assignments are due at 11:55pm and should be submitted through WebCT. No late homework or assignment is allowed without prior approval of the instructor.

Tentative Calendar of Assignments – Refer to the Gradiance Server for Home Works and Solutions

• Homework 1: Due 8/30 (point distribution: 3,3,3,3,3,3)
• Homework 2: Due 9/13 (point distribution: 3,6,3,3,3,3,3,3,3,3,3,3)
• Homework 3: Due 9/27 (point distribution: 6,6,3,3,6,6,6,3,3,3,3,3,6)
• Homework 4: Due 10/11 (point distribution: 3,3,3,3,3,3,3)
• Homework 5: Due 10/18 (point distribution 3,3,1,3,1,1,1,3,1)
• Project 1: Due 11/1
• Homework 6: Due 11/15 (point distribution 3,3,3,3,6,6,3,1,1,3,3,1)
• Project 2: Due 12/4
• Homework 7: Due 12/6 (point distribution 3,6,3,1,3,3,3,3)

Link to Project (tba)

Class Schedule (back to top)

• Tests are in class on Tuesdays 9/25 and 10/30. Tests are closed-book, but you are allowed to bring a one-page cheat sheet, which you must prepare yourself.
• Check often this webpage and Gradiance Server for news.
• All schedules are tentative and are subject to change.

CS3240 Class Schedule Outline

Week	Topic	Reading
1	Review of proof techniques, intro. to automata	1, 2.1 slides
2	Deterministic and nondeterministic finite automata	2.2--2.4 slides	HW1 due 8/30
3	Epsilon-NFA's, regular expressions	2.5, 3.1--3.3 slides
4	Properties of regular languages	3.4, 4.1, 4.2 slides	HW2 due 9/13
5	Algorithms for regular languages	4.2, 4.3
6	Equivalence and minimization of automata	4.4 slides	Test 1 9/25 Solutions HW3 due 9/27
7	Context-free grammars	5.1--5.3 slides
8	Ambiguous grammars, pushdown automata	5.4,slides	Fall Break 10/9 HW4 due 10/11
9	PDA/CFG equivalence, deterministic PDA's	6.1, 6.2 , 6.3	HW5 due 10/18
10	More on PDAs, Deterministic PDA's,	6.3, 6.4 slides
11	Chomsky-normal-form grammars Pumping lemma	7.1, 7.2 slides	Test 2 10/30 (Ch 1-6) Solutions
12	Closure properties for CFL's , Algorithms for CFL's,	7.3, 7.4 slides	PROJ1 due 11/8
13	Introduction to Turing machines , Variations of Turing machines	8.1-8.5 slides	HW6 due 11/15
14	Decidability, recursive and RE languages	9.1--9.3 slides	School Holiday 11/22
15	Project discussion. Some ``real'' undecidable problems	9.4, 9.5 (reading assignment only)
16	P, NP, and an intractable problem, NP-complete problems	10.1, 10.2, 10.3, 10.4	PROJ2 due 12/4 HW7 due 12/6
17	FINAL EXAM		Dec 12th (Wed) 11:30 - 2:20

Credits: part of the slides contents comes from previous GT editions of this course as well as from material posted at the textbook webpage http://infolab.stanford.edu/~ullman/ialc.html