LING 331: Theory of Computing
(Cross-listed with COM S). (3-1) Cr. 3. F.S.
Prereq: Minimum of C- in COM S 228, MATH 166, and in COM S 230 or CPR E 310; ENGL 250
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. Chomsky hierarchy and relations between classes of languages.