Regular expressions. Closure properties. Sequential machines and finite state transducers. State minimization. Chomsky hierarchy grammars, pushdown acceptors and linear bounded automata. Closure properties of algorithms on grammars. Turing machine as acceptor and transducer. Universal machine. Computable and noncomputable functions. Halting problem.

CSE 274 / CSE 606 or equivalent, and Discrete Math (MTH 231).

- Introduction
- mathematical preliminaries (1.0)
- set theory
- relations and functions
- recursive definitions
- mathematical induction

- mathematical preliminaries (1.0)
- Context-free grammars and parsing
- context-free grammars (1.5)
- regular grammars
- context-free grammars and languages

- parsing (1.5)
- left most derivations
- top-down parsing
- bottom-up parsing
- shift-reduce parsing

- normal forms (1.0)

- context-free grammars (1.5)
- Automata and Languages
- finite automata (1.0)
- deterministic finite automata
- state diagrams
- nondeterministic automata
- removing nondeterminism
- finite automata and regular sets

- regular languages and sets (2.0)
- regular grammars and finite automata
- nonregular languages
- pumping lemma
- closure of regular languages

- pushdown automata and context-free languages (1.0)
- pumping lemma for context-free languages
- closure properties of context-free languages

- turing machines (2.0)
- standard Turing machines
- Turing machines as language acceptors
- nondeterministic Turing machines
- equivalence of Turing machine variants

- the Chomsky hierarchy (1.0)
- context-sensitive languages
- linear bounded automata

- finite automata (1.0)
- Decidability (2.0)
- decision problems
- church-Turing hypothesis
- the halting problem
- universal Turing machine
- reducibility
- undecidable problems

- Exams/Review (1.0)

Students enrolled in CSE 573 will be given additional readings and/or assignments.

- Design and trace automata and grammars
- Design and trace finite state machines, pushdown automata, linear bounded automata, and Turing machines
- Describe and use non-deterministic automata
- Describe and use regular expressions
- Describe and determine the absolute and relative computational capabilities of automata variants
- Apply standard conversion algorithms to process automata and grammars
- Read and create proofs establishing the equivalence or non-equivalence of automata and/or grammars
- Design context-free grammars to describe a particular set of strings
- Describe and prove the closure properties of regular and context-free languages

- Describe the elements of the Chomsky hierarchy
- Describe the power and limitations of automata and grammars
- Describe the hierarchy of languages and grammars
- Describe the Church-Turing Thesis and its implications
- Prove that a language has a particular location in the Chomsky hierarchy

- Explain how some problems have no algorithmic solution
- Describe the basics of the theory of computation
- Provide examples of problems that are undecidable and unrecognizable
- Determine if a problem is decidable or recognizable
- Describe the operation of a Universal Turing Machine
- Describe the nature of the Halting problem and prove that it is undecidable and recognizable
- Demonstrate reducibility of one problem to another problem in proving that a problem is undecidable, recognizable, or decidable

Benton Hall, Room 205

650 E. High Street

Oxford, OH 45056

501 E. High Street

Oxford, OH 45056

- Campus Map
- Directions
- Online: Miami Online

- Main Operator 513-529-1809
- Office of Admission 513-529-2531
- Vine Hotline 513-529-6400
- Emergency Info https://miamioh.edu/emergency

1601 University Blvd.

Hamilton, OH 45011

- Campus Map
- Directions
- Online: E-Campus

- Main Operator 513-785-3000
- Office of Admission 513-785-3111
- Campus Status Line 513-785-3077
- Emergency Info https://miamioh.edu/regionals/emergency

4200 N. University Blvd.

Middletown, OH 45042

- Campus Map
- Directions
- Online: E-Campus

- Main Operator 513-727-3200
- Office of Admission 513-727-3216
- Campus Status 513-727-3477
- Emergency Info https://miamioh.edu/regionals/emergency

7847 VOA Park Dr.

(Corner of VOA Park Dr. and Cox Rd.)

West Chester, OH 45069

- Main Operator 513-895-8862
- From Middletown 513-217-8862
- Emergency Info https://miamioh.edu/regionals/emergency

Chateau de Differdange

1, Impasse du Chateau, L-4524 Differdange

Grand Duchy of Luxembourg

- Main Operator 011-352-582222-1
- Email luxembourg@MiamiOH.edu
- Website https://miamioh.edu/luxembourg

217-222 MacMillan Hall

501 E. Spring St.

Oxford, OH 45056, USA

- Main Operator 513-529-8600
- Emergency Info https://miamioh.edu/emergency

© 2023 Miami University All Rights Reserved