CSE 457/598 Fall 2014
Theory of Formal Languages Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/457syllabusf14.html

CSE 457 is a second course in the theory of formal languages. Students who complete this course can
  1. Understand the computational capabilities of different types of finite state machines for language recognition, language generation, and language transduction.
  2. Understand operations on regular languages that preserve regularity, including morphisms, inverse morphisms, substitutions, and quotients.
  3. Understand the characterization of regular languages via the Myhill-Nerode theorem.
  4. Employ the characterization of regular languages to minimize the number of states in a deterministic finite automaton to recognize a language.
  5. Understand the periodic nature of regular and context-free languages, through the pumping lemmas and Parikhs theorem.
  6. Apply their understanding of the structure of regular and context-free languages to devise computational models for process control, parsing, and pattern recognition.

Topics to be Covered:

The primary learning objectives of CSE 457 are to address two objectives of the CS major in more detail than is treated in CSE 355, namely (1) apply knowledge of computing and of mathematics appropriate to Computer Science, and (2) apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of software and demonstrate the comprehension of the tradeoffs involved in design choices.

The grading for undergraduates in the class is as follows:

The goal is to learn the material, and grades are meant to be reflective of how well you learned it. For this reason, the final exam is more heavily weighted, and is cumulative. If your percentage grade on the final exam exceeds that on the midterm, the final exam grade replaces the midterm exam grade in calculations of the final course grade. You must write the midterm exam in order for the grade to be eligible for replacement. It does not replace homework grades. It is imperative that you make a legitimate attempt to answer all of the homework questions. Any scaling of grades at the end of the course takes into account the effort invested.

The grading for graduate students in the class is as follows:


Undergraduates preferring the graduate course workload should speak to the instructor to see if the requirements can be varied to accommodate their interests. Approval for undergraduates to pursue projects must be obtained by the end of September at the latest, or the student will be assumed to be following the undergraduate requirements.

General Course Information:

Students may discuss homework assignments with their classmates; however all work turned in is expected to be that of the individual. If you have any questions regarding appropriate collaboration please see the instructor. Penalties for plagiarism and other forms of academic dishonesty can include a grade of zero on the offending item, a reduction of the final letter grade in the course, or both. Infractions can result in failure in the course with a transcript designation of academic dishonesty. Repeat offenses can result in expulsion from the program.

We will follow the text closely, but the emphasis on the tests will be the same as that in the lectures. Hence, although class attendance is not required, it is highly recommended.