COT 6315/CM 710-R Formal Languages and Computation Theory
Last Edited: Thu Oct 16 14:33:46 1997 by jnw (Joseph N. Wilson) on nighthawk.cise.ufl.edu
Syllabus
- Semester Credit Hours:
- 3
- Number of Lecture Hours:
- 39 (50 minute) lectures
- Class Meeting Time
- MWF 2nd Period (8:30 - 9:20)
- Instructor
- Joseph N. Wilson
(jnw@cise.ufl.edu)
Room E314A CSE Bldg. (Overlooking the French Fries.)
Phone: (352) 392-1360
Office Hours: TBA
- For Academic Questions Contact:
- Joseph N. Wilson (352) 392-1360 FAX (352) 392-1220
- For Administrative Questions Contact:
- Art Zirger (352) 392-9670 FAX (352)392-1724
- Prerequisites:
- COP 3530 (Data Structures) and familiarity with
discrete mathematics and data structures
- Textbook
-
Michael Sipser,
Introduction to the Theory of
Computation, PWD Publishing Company, 1997, ISBN
0-534-94728-X.
- Course Objectives
- To become familiar with the fundamentals of automata theory,
formal languages, Turing machines and computability.
- Course Description
- Introduction to theoretical computer science including formal
languages, automata theory, Turing machines, and computability.
- Course Requirements:
-
- Homework (30%)
- One assignment per class (after the first class)
- Three Midterm Examinations (15% Each)
-
- Final Examination (25%)
-
- Course Outline by Topical Areas:
- The course is divided into four major sections dealing with
- Introductory Mathematical Foundations, Regular Languages
and Finite State Machines
- Context-Free Languages and Pushdown Automata
- Turing Machines, Unrestricted Languages, and
Decidability
- Reducability, and Computability Theory
Detailed Outline:
- Mathematical Notation and Foundations
- Constructing Proofs
- Finite Automata
- Nondeterministic and Deterministic Finite Automata
- Regular Expressions
- Proving a Language to be Nonregular
- Context-free Grammars
- Pushdown Automata
- Proving a Language to be Non-context-free
- Turing Machines
- Variants of Turing Machines
- Relation Between Algorithms and Turing Machines
- Decidability
- The Halting Problem
- Undecidable Language Problems
- Post's Correspondence Problem
- Mapping Reducibility
- The recursion Theorem
- Decidability of Logical Theories
- Turing Reducibility
- Information Representation