|
Search our Site
ON THIS PAGE:
Course Objectives
Prerequisites
Approach
Typical Text
Course Outline
|
|
COMP 455 [181]: Models of Languages
and Computation
(3 hours)
Syllabus approved 3 May 1988
Course
Objectives
Give the student the ability to do the following.
- List and define the major terms and concepts, and demonstrate some
intuition in the area
- Demonstrate familiarity with the major theorems and results. Be able
to prove several of the most basic and important theorems (or at least
outline the proof).
- Apply the definitions and basic results to a new situation extending
definitions and results appropriately.
- Prove (for example):
- A language regular or context-free by construction.
- A language non-regular or non-context-free by the pumping
lemmata and/or closure properties of the language class.
- Existence of languages outside of the Chomsky Hierarchy by
diagonalization.
- A problem unsolvable by reduction from the halting problem.
- Examine an incorrect proof and pinpoint the fallacy.
- Define top-down and bottom-up parsing strategies.
- Write a paragraph discussing the application of a concept from this
course to some nontheoretical area of computer science (other than an
application discussed in class).
Prerequisites
MATH 381 and COMP 110 (or 121) are hard prerequisites. More specifically,
prerequisite topics include discrete mathematics: exposure to relations,
set notation and graphs; programming in some standard imperative language;
elementary logic and predicate calculus, boolean functions and truth tables.
Approach
Traditional: lectures and homework.
Typical Text
Lewis and Papadimitriou, Elements of the Theory of Computation
(6th printing or later), Chapters 1-7.
Course Outline
Basic Concepts (0.5)
- Operations on and specifications of Sets
- Properties of Relations and Functions
- Proof Techniques
Languages and Machines (1)
- Specification and Representation
- Generation vs. Recognition
- Grammars and machines
- Unrecognizable Languages
Regular Languages and Finite Automata (2.5)
- Regular Expressions
- Deterministic and nondeterministic FA
- Regular Sets and closure properties
- Equivalence of FA and regular expressions
- Pumping lemma and non-regular sets
Context-Free Languages, Grammars and Pushdown Automata (3)
- Context-free grammars and PDA
- Properties and associated algorithms for CFLs
- Pumping Lemma for CFL
- Deterministic PDA
- Top-down and bottom-up parsing
Computable Functions and Turing Machines (2.5)
- Deterministic and Nondeterministic TM
- Chomsky Hierarchy of machines and grammars
- Computable total and partial functions
- Church's Thesis
- TM encoding
- Universal TM
Uncomputability (2.5)
- Halting problem
- Turing reducibility and undecidable problems
Computational Complexity Topics (1.5)
- Algorithm analysis on a TM
- Polynomial time complexity
- Nondeterministic Polynomial time complexity
- Polynomial-time reducibility and NP-completeness
- P ?= NP
|
