CSE 473/573 Automata, Formal Languages, and Computability (3)

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.

Prerequisite: CSE 274 and MTH 231.

Back to top