Description
To provide a rigorous mathematical framework for two general areas: that of language description and that of computation; to examine the relation between the two and to consider practical applications from Computer Science and Linguistics. Computability theory and complexity theory are also introduced. Students who plan to pursue a graduate degree incomputer science are strongly encouraged to take 01:198:452.
Credits: 3†
01:198:344.
Please note that courses for which a student has received a grade of D cannot be used to satisfy prerequisite requirements.
Semesters Offered:Spring
Topics: Regular languages and automata
Context-free languages and Pushdown Automata
Turing Machines and Decidability
Hierarchies and properties of language families
Computational Complexity Theory
Expected Work: weekly homework
Exams: 1 midterm and a final exam
† - Can be taken for graduate credit.
