[CE160 homepage]

CE 160 Automata and Formal Languages

First Semester, 2002-2003

Class schedule: 
	CE 160 A:	TTh,  1500-1630,  F304
	CE 160 B:	TTh,  1630-1800,  F304

Course Timetable:

(This timetable is updated on a best effort basis.)

	Tuesday	Thursday
June	18 central concepts of automata theory	20 introduction to deterministic finite automata Exercise 2.2.1(a): A marble-rolling toy Homework for June 25: (part of) 2.2.1(c) Redo 2.2.1(a) if the levers reversed before letting the marble pass.
	25	27
July	2	4
	9	11
	16 No classes in relation to village elections of July 15	18 [1st exam] coverage: deterministic automata, nondeterministic finite automata, regular expressions
	23 proof of pumping lemma for regular sets example exercise 4.1.2.b, p.30 (sec 4.1 Pumping Lemma for Regular Languages)	25 homework due: 4.1.2.e               (use of pumping lemma) topic: pumping lemma for regular languages quiz on pumping lemma reading assignment: sec 4.1
	30 due: homework on pumping lemma topic: closure and decision properties of regular languages quiz: closure properties reading assignment: secs 4.2, 4.3
August		1 due: homework on minimization of automata topic: closure and decision properties of regular languages, minimization of automata quiz: decision properties reading assignment: secs 4.1, 4.2
	6 due: homework on equivalence and minimization of automata topic: equivalence and minimization of automata quiz on minimization of automata reading assignment: 4.4	8 due: homework on context-free grammars topic: context-free grammars (CFGs), parse trees quiz: parse trees reading assignment: 5.1 to 5.3
	13 classes suspended due to some rains	15 due: homework on CFGs topic: CFGs, parse trees quiz: CFGs reading assignment: 5.1 to 5.3
	20 due: homework on parse trees topic: ambiguity in context-free grammars and languages quiz: ambiguous grammars reading assignment: 5.4	22 2nd exam (tentative) coverage: pumping lemma for regular languages, closure and decision properties of regular languages, minimization of automata, context-free grammars and parse trees, ambiguity in context-free grammars
	27 reading assignment: 6.1 introduction to pushdown automata (PDAs)	29 reading assignment: 6.2, 6.3 languages associated with PDAs equivalence of PDAs and CFGs
September	3 reading assignment: 6.4 Deterministic PDAs	5 reading assignment: 7.1 normal forms for CFGs
	10 reading assignment: 7.2 pumping lemma for context-free languages (CFLs)	12 reading assignment: 7.2 pumping lemma for CFLS
	17 reading assignment: 7.3 closure properties of CFLs	19 reading assignment: 7.4 decision properties of CFLs
	24 3rd exam (tentative)	26 reading assignment: 8.1, 8.2 introduction to Turing Machines (TMs)
October	1 reading assignment: 8.3 programming techniques for TMs	3 reading assignment: 8.4 extensions to the basic TMs
	8 reading assignment: 8.5 restricted TMs	10 reading assignment: 8.6 TMs and computers
	Finals Week: October 14 - 19 4th exam

 

 

Textbook:

John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, 2nd ed, 2001.
ISBN: 0-201-44124-1
[textbook's home page] with links to similar courses taught by the authors.

Course Outline: (covers approximately Chapters 1 to 8 of the textbook)

Central concepts of automata theory 		[Chapter 1]
Finite automata					[Chapter 2]
	Deterministic Finite Automata (DFAs)
	Nondeterministic Finite Automata (NFAs)
	Finite automata with epsilon-transitions (e-NFAs)
	Equivalence of e-NFAs, NFAs, and DFAs
Regular expressions and languages		[Chapter 3]
	Regular expressions
	Conversion between finite automata and regular expressions
								First exam
Properties of regular languages			[Chapter 4]
	The pumping lemma for regular languages
	Equivalence and minimization of finite automata
Context-free grammars and languages		[Chapter 5]
	Context-free grammars (CFGs)
	Derivations and parse trees
	Ambiguity
								Second exam
Pushdown automata				[Chapter 6]
	Definition of the pushdown automaton (PDA)
	Languages associated with PDAs
	Equivalence of PDAs and CFGs
Properties of context-free languages (CFLs)	[Chapter 7]
	Normal forms for CFGs
	The pumping lemma for CFLs
	Closure and decision properties of CFLs
								Third exam
Introduction to Turing machines			[Chapter 8]
	The Turing machine (TM)
	Instantaneous descriptions and transition diagrams for TMs
	Languages associated with TMs
	Extensions to the basic TM
	Turing machines and computers
								Fourth exam

The best computer is the one between your ears.

This page has been accessed

times since June 22, 2002.