CMPS 479 - Course Syllabus

I. Course Description: CMPS 479 – Automata and Formal Languages.

Credit 3 hours. Prerequisite: Computer Science 257 or Mathematics 223 and senior standing. Introduction to computing device capabilities through study of abstract machines and corresponding formal languages. Topics include Turing machines, recursion, Chomsky grammars, context-free languages, regular languages, and finite automata.

II. Instructor: Dr. Cris Koutsougeras

 Office: Fayard Hall, Room 307C
 Office Phone: (985) 549-2189
 Email Address: ck (at of course)

Office Hours: 2:30 – 3:30 Wednesday, 13:00 – 14:00 Tuesday and Thursday, and by appointment. You are also welcome to just drop by during the day. If I am not on a deadline, I'd be happy to take some time with you.

III. Course content



  • Regular languages
  • Finite State Machines (FSM)
  • Regular expressions
  • Pumping lemma for regular languages
  • Push down automata (PDA)
  • Context free grammars and parsing
  • Normal forms (Chomsky, Greibach)
  • Equivalence of Grammars and PDAs and applications to Compilers
  • Non-determinism (both with respect to FSMs and PDAs)
  • Pumping lemma for context free languages
  • Turing Machines
  • Generalized grammars
  • Halting problem, Computability/Enumerability, Decidability
  • The Church-Turing thesis
  • Properties of language combinations (concatenation, union, intersection, quotient, etc)
  • Diagonalization

Learning Objectives: Students will be able to:

  • Discuss the concept of finite state machines.
  • Design a deterministic finite-state machine to accept a specified language.
  • Explain context-free grammars.
  • Determine a language’s location in the Chomsky hierarchy (regular sets, context-free,context-sensitive, and recursively enumerable languages).
  • Prove that a language is in a specified class and that it is not in the next lower class.
  • Convert among equivalently powerful notations for a language, including among
  • DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
  • Explain at least one algorithm for both top-down and bottom-up parsing.
  • Explain how a compiler can be constructed for a simple context free language
  • Distinguish the concepts of computability and decidability
  • Explain how some problems have no algorithmic solution.
  • Provide examples that illustrate the concept of uncomputability.
  • Explain the Church-Turing thesis and its significance.


This course deals with the following major questions:

  • Can we define our intuitive notion of the concept of computation
  • What can be computed via mechanisms that are defined by discrete structures
  • How powerful are the various classes of discrete computing structures and what are the properties of problems that each class can handle
  • Is there a computer which can universally solve problems or are there problems that cannot be solved by discrete computing mechanisms

This course presents what we know about the notion of “computing” and mechanisms to perform computing independently of the underlying physical structure that may be used for building a computer. It revolves around fun philosophical issues of the form: can we prove or disprove the validity of the statement “I am lying”. This course explains why all the problem solving methods essentially boil down to search algorithms. The course provides essential foundation for the science of computing.

IV. Course Requirements:

 A. Required Text and other materials:

  • Text: Automata, Computability and Complexity, 3rd Edition, by Elaine Rich. 
  • Internet Access and Computing Facilities: Internet access is not required for this class. However, for class communication, and according to Southeastern University policy, students are expected to check their SELU-provided email accounts, as well as the class web site on BlackBoard, at least once every week, more often if possible. If you wish to have Internet access from off-campus, you will have to provide for Internet service at your own expense. 

 B. Class Schedule and Place: Tuesdays, Thursdays, 11:00 – 12:15 in Fayard 213.

C. Probable Test Dates: February 26, March 25.

D. Assignments: There will be a number of assignments, usually at least one every other week. Exact requirements and due date will be given with each assignment. All assignments must be turned in either electronically or in a formatted and printed form. Unless prior permission has received by the instructor, assignments which are late (see “Late Assignments”, below) will receive reduced credit during the first week but no credit after that. Your lowest one assignment grade will be dropped, and the remainder will be used to compute your total assignment grade.

E. Required Reading: Much of the content of this course is obtained through reading the textbook and other online/handout materials. You should make particular effort to not miss classes because the order of the material presentation may not be exactly as in the textbook and some limited material may not even be found in the textbook. Quizzes over the reading will be done at regular intervals, will be evaluated for participation, and are a small part of your grade.

F. Attendance Policy: Attendance will be taken each day, as required by the University Regulations. This policy may be found in the Undergraduate Catalog, and you should make yourself familiar with it. In particular, note that excessive unexcused absences are considered 10% of the total classes, which for this semester and class is three (3) classes. According to the University Regulations, this may result in your being withdrawn from class by the instructor. This is not automatic however, so you should consult the instructor if you think you may have been withdrawn from class. Do not assume that you will be automatically withdrawn from class for non-attendance. Even if you are allowed to continue, please understand that your grade will suffer from lack of attendance. You will miss material that is only available in class, and classroom participation is crucial to your success in this class. In the event of an excused absence, you are responsible for providing acceptable documentation and making arrangements for making up for the lack of participation. Every student is responsible for anything covered in class, even if it is not in the text. This includes announcements of assignments or test dates, so if forced to miss class, be sure to contact the instructor and ask to be informed of those announcements.

G. Withdrawal from Class: The last day you may withdraw or resign from this class is Friday, October 19, 2007.

H. Accommodation of Disabilities: If you are a qualified student with a disability seeking accommodations under the Americans with Disabilities Act, you are required to self-identify with the Office of Disability Services, Room 203, Student Union.  No accommodations will be granted without documentation from the Office of Disability Services.

I. Class Decorum: Free discussion, inquiry, and expression is encouraged in this class.  Classroom behavior that interferes with either (a) the instructor’s ability to conduct the class or (b) the ability of students to benefit from the instruction is not acceptable.  Examples may include routinely entering class late or departing early; use of beepers, cellular telephones, or other electronic devices; repeatedly talking in class without being recognized; talking while others are speaking; or arguing in a way that is perceived as “crossing the civility line.”  In the event of a situation where a student legitimately needs to carry a beeper/cellular telephone to class, prior notice and approval of the instructor is required. In an online class, like this one, civility is expected in your online communications and website submissions. Offensive themes and language, “adult” materials, or obscenity is not appropriate in materials submitted for this class.

J. Children in Class: It is the policy of the University that the classroom is not a place for children, and that students are not to bring their family members for day care or baby sitting. (Since this class does not meet physically, this policy should have little effect.)

K. Email Communication: University email policy reads (in part) as follows, "[Faculty] Uses of nonSoutheastern email addresses for communication with students regarding University business or educational matters are not acceptable...."  In compliance with this policy, please use only your SLU email address when contacting me about the course.  I will not respond to nonSLU email addresses in any professional capacity.  Recall that your SLU email accounts are accessible through the Internet via "WebMail" which can be reached from the SLU homepage:

L. Plagiarism: In the event that essays or papers are required as part of any assignment in this class, you should be aware that plagiarism will not be tolerated, and may be detected through the use of Students agree by taking this course that all required papers may be subject to submission for textual similarity to for the detection of plagiarism. All submitted papers will be included as source documents in the reference database solely for the purpose of detecting plagiarism of such papers. Use of the service is subject to the Terms and Conditions of Use posted on the website.

M. Changes in Requirements: Due date changes, test postponements, etc. will be announced on BlackBoard. In case of emergencies, I may attempt to contact you by phone, so please make sure that I have your phone number, and let me know if it changes. Notices may also be given by email, or on the class World Wide Web page. This syllabus will be posted on the class World Wide Web page, and that copy will always be the official copy, even if changes are necessary.

  • V. Course Assignments: Provided Separately.

VI. Evaluation Procedure

  • A. Late Assignments: Assignments are due at the time specified in the assignment. Late assignments will be accepted only until a week after the deadline; there will be no credit for assignments that are later than a week. However one assignment grade will be dropped at the end of the class. No assignments of any sort will be accepted after 2:00 p.m. on the last official day of classes, even if this would result in a failing grade.
  • B. Grade Calculation: Your grade will calculated according to the following point distribution:
    • 20% Assignments
    • 5% Quizzes
    • 50% Midterms (25% each)
    • 25% Final Exam

     Grades will be computed by a curve method. In the event that the distribution does not present enough breaks or if it has too many breaks, letter grades should be approximately expected according to the following chart which is only given as an indication of probable expectations:

     A      B     C     D  F

     90-100 80-89 70-79 60-69 0-59

  • VIII. Academic Integrity:

Learning is a social experience, and I wouldn't dream of trying to change that. Studying with friends, and talking among yourselves about how to attack a problem is important to success in this class. But if you don't do your own thinking -- if you only take from these discussions, and never give -- then you won't understand well enough to perform on tests. That's enough to ruin your grade in this class. Make sure that your work is your own, because you might have to pass a quiz over the content of your assignment to receive credit. If a project is supposed to be done by a group, it will be specifically announced that way. And if you need further help, please talk to me. I try to be as accessible as I know how. If you can't make my office hours, send me an email – if I'm not covered up with something, I'll be glad to work with you. And if we need to, we can make a special appointment.

More formally, students are expected to maintain the highest standards of academic integrity. Behavior that violates these standards is not acceptable. Examples are the use of unauthorized material, communication with fellow students during an examination, attempting to benefit from the work of another student and similar behavior that defeats the intent of an examination or other class work. Cheating on examinations, plagiarism, and improper acknowledgement of sources in essays and the use of a single essay or paper in more than one course without permission are considered very serious offenses and shall be grounds for disciplinary action as outlined in the current General Catalogue.

IX. Important dates to note

The following dates should be noted:

    • Thursday, February 14 is the last day to withdraw or resign from Term I classes.
    • Friday, March 14 is the last day to withdraw or resign from regular classes.
    • Thursday, May 1 is the last day to withdraw or resign from Term II classes.
    • Monday, May 19 is the last day to return rental textbooks without a fine.