Skip to content Skip to navigation

Formal Languages and Automata

01:198:452

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
Prerequisite: 

01:198:344.

Please note that courses for which a student has received a grade of D cannot be used to satisfy prerequisite requirements.

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
Learning Goals: 
Computer Science majors ...
  • will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).
  • will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.
  • will be prepared for the next step in their careers, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).
Semester: 
Spring
Course Type: 
Undergraduate

Check the University Schedule of Classes to see if this course is open.

Request an Special Permission Number here if the class is full.