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
 Understand the computational capabilities of different types of finite state machines for language recognition, language generation, and language transduction.
 Understand operations on regular languages that preserve regularity, including morphisms, inverse morphisms, substitutions, and quotients.
 Understand the characterization of regular languages via the MyhillNerode theorem.
 Employ the characterization of regular languages to minimize the number of states in a deterministic finite automaton to recognize a language.
 Understand the periodic nature of regular and contextfree languages, through the pumping lemmas and Parikhs theorem.
 Apply their understanding of the structure of regular and contextfree languages to devise computational models for process control, parsing, and pattern recognition.
Topics to be Covered:
 Shallit: primarily Chapters 1, 3, 4, 7
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:

Homework Assignments  five at 8% each  40%
Always due at the start of class.
Written documentation detailing medical treatment or a family emergency is required in order to make alternate arrangements for homework submission.
Homework 1 (Out: 27 August Due: 15 September Returned: 24 September)
Solutions distributed in class.
Grades for undergrads out of 50 are: 7 21 34 45 49 49.
Grades for graduate students out of 50 are: 8 14 14 14 14 16 20 20 21 22 24 25 28 29 31 32 34.
Homework 2 (Out: 15 September Due: 29 September Returned: 06 October)
Solutions distributed in class.
Grades for undergrads out of 40 are: 6 11 16 33 36 40 40.
Grades for graduate students out of 40 are: 9 12 13 13 16 17 17 21 21 22 22 22 23 24 27 28 29.
Homework 3 (Out: 29 September Due: 20 October Returned: 29 October)
Grades for undergrads out of 50 are:
9 12 23 26 42 43 43 44.
Grades for grads out of 50 are:
6 19 19 20 21 21 22 24 24 30 32 33 34 36 39
Solutions distributed in class.
Homework 4 (Out: 22 October Due: 05 November Returned: 19 November)
The homework was out of 50, but treat your grade as out of 40.
Grades for undergrads out of 40 are:
2 15 16 30 34 41 41
Grades for grads out of 40 are:
7 10 14 17 18 18 22 25 26 26 27 27 29 30
Solutions distributed in class.
Homework 5 (Out: 03 November Due: 24 November Returned: 03 December)
Undergraduate grades out of 50 are:
12 22 41 43 44 45
Graduate grades are:
5 14 16 18 19 25 26 28 29 30 34 35 35 35 37 40
Preliminary solutions distributed in class, Corrected ones are here for the moment.
 Midterm Exam (Open Book and Notes)  20%  inclass date 22 October
Grades out of 50. Undergraduates:
9 10 14 29 30 32 37 49
Graduates:
11 16 18 18 20 21 23 23 24 25 25 26 27 29 29 32 37
 Final Exam (Open Book and Notes)  40%  in class date 08 December, 12:102:00 p.m.
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:

Homework Assignments  five at 6% each  30%
(due dates same as undergrads)
 Midterm Exam  15%  as above
 Final Exam  30%  as above
 Project  25%  Due 03 December.
The individual project topic is to be selected prior to 20 October, and should concern an area in which the theory of formal languages is applied (e.g., network protocols, natural language understanding, coding theory, software correctness).
The project is an individual effort enabling the student to explore applications that the course cannot treat.
An 810 page wellresearched document is expected.
Shallit's book suggests possible projects at the end of each chapter.
Grades out of 25 are:
15 16 16 16 16 17 17 18 19 19 20 20 21 22 22 22
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.