# MAT 361 Finite Automata

Instructor:
Office:
Office hours:
Phone:
Email:

### Course Description

Study of the abstract formalization of digital computers. Applications to computation theory and formal linguistics.

MAT 361 meets for three hours of lecture per week.

### Prerequisites

Prerequisite: MAT 281 or equivalent with grade C or better. Students must be familiar with sets, functions, relations, proofs -- including proof by induction and by contradiction.

### Objectives

The purpose of this course is to provide the student with an understanding of what computers (general-purpose symbol manipulating machines) can (and cannot) do; in short the theory of what is computable. In addition (because it turns out to be related to the taxonomy of symbol manipulating machines) a taxonomy of languages is developed.

After completing MAT 361 the student should be able to

1. Define the following terms:
• Language over {a,b}
• Regular language
• Regular expression
• Context free language (CFL)
• Transition graph (TG)
• Deterministic finite state acceptor/automaton (DFSA)
• Nondeterministic finite state acceptor (NDFSA)
• Deterministic pushdown acceptor (DPDA)
• Nondeterministic pushdown acceptor (NPDA)
• Post machine (PM)
• Turing machine (TM)
• Recursive language
• Recursively enumerable (r.e.) language
• Transducer
• Phrase structure grammar
• Regular grammar
• Context free grammar (CFG)
• Chomsky Normal form of a grammar (CNF)
• Universal Turing machine (UTM)
• Chomsky hierarchy of languages
2. State the following:
• Kleene's Theorem
• The pumping lemma for regular languages.
• Myhill-Nerode Theorem
• The pumping lemma for context free languages.
• Turing's hypothesis
• Church's thesis.
• Turing's halting problem
3. Given a language described by any of the following provide a definition of that language using any of the others: DFSA, NFSA, regular expression, regular grammar, TG.
4. Given a language described by either of the following, provide a description using the other: NPDA, CFG.
5. Be able to use the appropriate pumping lemmas and/or the theorem of Myhill-Nerode to prove a language is not regular or is context sensitive.
6. Given a CFG find an equivalent grammar in CNF

### Expected outcomes

Students should be able to demonstrate through written assignments, tests, and/or oral presentations, that they have achieved the objectives of MAT 361.

### Method of Evaluating Outcomes

Evaluations are based on homework, projects, class participation, short tests and scheduled examinations covering students' understanding of topics covered in MAT 361.

### Text

Introduction to Computer Theory (2nd ed.), by D. Cohen. Wiley 1997.

#### Course Outline

• Sets, relations and functions; proofs;(review material)
• Languages (syntactically defined by various methods)
• Machines (acceptors and transducers, finite state and pushdown automata, Post and Turing machines, determinism)
• Grammars (phrase structure, context free, Chomsky normal form, parsing strings)
• Chomsky hierarchy and examples of each class
• Closure properties (union, complement, product, decision problems)
• Pumping lemmas and the theorems of Kleene, McCarthy, Myhill-Nerode
• Universal Turing machines and the Halting problem

Students' grades are based on homework, projects, class participation, short tests, and scheduled examinations covering students' understanding of the topics covered in MAT 361. The instructor determines the relative weights of these factors.

### Attendance Requirements

Attendance policy is set by the instructor.

### Policy on Due Dates and Make-Up Work

Due dates and policy regarding make-up work are set by the instructor.

### Schedule of Examinations

The instructor sets all test dates except the date of the final exam. The final exam is given at the date and time announced in the Schedule of Classes.