[CE 160 homepage]

CE 160, 1st semester 2002-2003

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 3, 2002.