CIS 625: Introduction to Automata and Formal
Languages
Description
Machine based and formal grammar based models of computation. Finite
automata, regular languages. Context-free languages, pushdown
automata. Turing machines. Church-Turing thesis. Introduction to the
halting problem.
Level, Credits, Class Time Distribution, Prerequisites
| Level |
Credits |
Class Time Distribution |
Prerequisites |
|
U |
3 |
Three one-hour lectures |
CIS 321 and Math 366 |
Quarters Offered, General Information, Exclusions, Cross-Listings, etc.
Objectives
- Master using regular expressions, and finite state machines.
- Master using context-free languages, and push-down automata.
- Be familiar with using Turing machines as a general computational model.
- Be familiar with the Church-Turing thesis.
- Be exposed to the unsolvability of the halting problem.
- Be exposed to using context-free grammars in compiler construction.
Texts
- E. Gurari, An Introduction to the Theory of Computation,
Computer Science Press, 1989.
| Relationship to ABET Criterion 3 |
Relationship to CSE Program Objectives |
| a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
| XXX |
|
|
|
XX |
|
|
|
X |
|
|
|
| 1a |
1b |
1c |
2a |
2b |
3a |
3b |
3c |
4a |
4b |
| XX |
XXX |
XX |
|
|
|
|
|
|
XXX |
|
Topics
| No. of Weeks |
Topics |
|
1 |
General concepts |
|
4 |
Finite-state automata and regular languages |
|
2 |
Push-down automata and Contex-free languages |
|
1 |
Turing machines |
|
2 |
Pumping lemmas and undecidability |
Representative Lab Assignments
This course does not have any lab assignments.
Grading Plan
| Homeworks |
25% |
| Midterm Exams |
40% |
| Final Exam |
35% |
Preparer Information and Date:
Syllabus prepared by Eitan Gurari, last modified April 30, 1999.