LING 3310: Theory of Computing
(Cross-listed with COMS 3310).
Credits: 3. Contact Hours: Lecture 3, Discussion 1.
Prereq: (COMS 2300 or CPRE 3100) and (Minimum of C- in COMS 2280, ENGL 2500, and MATH 1660)
Models of computation: finite state automata, pushdown automata and Turing machines. Study of grammars and their relation to automata. Limits of digital computation, unsolvability and Church-Turing thesis. Relations between classes of languages.
(Typically Offered: Fall, Spring)