COMP 454 – Automata, Languages and Computation – Fall 2015

Course Syllabus

  • Course URL:
  • CI Catalogue URL:
  • Instructor: Michael Soltys <>
  • Twitter: @MichaelMSoltys
  • Course Outline: This course is an introduction to the theory of computation, from the point of view of languages over finite alphabets. We are going to start with Regular Languages, and the equivalence of several definitions: Finite Automata (deterministic and non-deterministic) and Regular Expressions (and applications to text search). The Pumping Lemma, and other approaches to showing that languages are not regular. We will continue with Context-free languages, and again the equivalence of several definitions: Context-free grammars and Push-Down Automata. We will finish with a version of the Pumping Lemma for Context-free languages. The final topic will be the Church-Turing thesis, and decidability.
  • Lectures: MW 12:00-1:15 in Sierra Hall 1131
  • Textbook: Introduction to the Theory of Computation, by Michael Sipser, 3rd edition
  • Grading: Six assignments worth 10% each, and a final exam worth 40%. The assignments will consist in a selection of problems from the textbook. The assignments have to be completed in groups of at least two, and no more than three. It would be best if you formed a group at the beginning of the course, and worked on all the assignments with the same group. There is tremendous value in working on problems with your group; it amplifies the learning experience, and teaches teamwork. The instructor will grade one or two “random” problems from the assignment. The final exam will be written individually.
  • How to avoid plagiarism: As mentioned above, the assignments will be written in groups. Each group has to work independently of the other groups; verbal discussions of problems among groups are allowed, but you should not show written notes, and you should not leave such discussions with written notes.
  • Attendance: Students are encouraged but not required to attend the lectures. The assignments will be posted online. The final exam will be written in class.
  • Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.
  • Check this web page regularly for announcements.

Announcements and class diary

  • Dec 7: Exam Part 2/2 (Context-free Languages).
  • Dec 2: Exam Part 1/2 (Regular Languages).
  • Nov 30: Review of the course material.
  • Nov 25: No lecture, questions session in the usual classroom.
  • Nov 23: We discussed the solutions to Assignment 5, especially question 2.43: if A is regular, then SCRAMBLE(A) is a CFL. We then finished the course with a discussion of deterministic CFGs.
  • Nov 18: We introduced Deterministic PDA, DPDA, and the concept of a deterministic context-free language; basic definition and applications to compiling.
  • Nov 16: We discussed the solutions to Assignment 4, and we covered the Pumping Lemma for Context Free languages.
  • Nov 9: We discussed at length the solution to Quiz 8.
  • Nov 4: Quiz 8. We proved the correctness of the transformation from a PDA to a CFG. The main idea is the semantics of the variables A_pq: variables from which one can generate all strings that take P in state p with empty stack to P in state q with empty stack. The proof involve induction on number of steps in derivation, and induction on number of steps in computation. This is one of the more sophisticated ideas of the course.
  • Nov 2: no class
  • Oct 28: Quiz 7, on Chomsky Normal Form. We start showing how to construct a grammar G_P from a given PDA P so that L(G_P)=L(P). The following exercises were given as practice to understand this technical material: 2.7,10,11,12. We will continue on Wednesday Nov 4, as there is no class on Nov 2.
  • Final Exam Information: the final will be written in two parts in the classroom, on Wednesday December 2 (part 1/2) and on Monday December 7 (part 2/2). To prepare for the exam, review the lectures notes, and especially the problems and solutions from the assignments and quizzes.
  • Oct 26: Started with Quiz 6. We started showing that PDAs describe CFLs. We showed that a CFG G can be simulated with a PDA; given a CFL L with a CFG G, there exists a P_G such that L=L(G)=L(P_G).
  • Oct 21: Definition of Push Down Automata (PDAs), as an NFA with a stack. Example of a run, and definition of acceptance. We looked at the formalism of pushing, popping, and padding the input with epsilons.
  • Oct 19: Review of solutions for Assignment 2.
  • Oct 14: Discussed the details of transforming any CFG into Chomsky Normal Form (CNF). We linked this important idea with the CYK Dynamic Programming Algorithm.
  • Oct 12: Started chapter 2: Context-Free languages; definitions and examples: CFG, derivations and parse-trees; left-most parse-tree and ambiguity.
  • Oct 7: Quiz 5, based on exercises 1.21 and 1.28, which were assigned as homework. We then spoke about the more challenging parts of assignment 2 which is due (after an extension) on Monday Oct 12.
  • Oct 5: Covered in detail the Pumping Lemma; proof, and examples of applications.
  • Sep 30: Quiz 4; finished discussing the solutions to the problem of Assignment 1.
  • Sep 28: Started discussing the solutions to the problems in Assignment 1.
  • Sep 23: Quiz 3; converting an NFA into a regular expression: NFA into GNFA into Reg Exp. Do exercises 1.21,28.
  • Sep 21: Regular Expressions; defintion and examples. Every RE can be represented with an NFA – the proof uses the same ideas as the proof of closure properties of regular languages.
  • Sep 16: Work on Assignment 1
  • Sep 14: Quiz 2, consisting in translating an NFA into a DFA (based on exercise 1.16). We then show that regular languages are closed under concatenation and Kleene’s star, completing the basic closure properties. Please do exercise 1.20 in preparation for lecture on Sept 16.
  • Sep 9: NFA – Non-deterministic Finite Automata. Do exercise 1.16 to train your understanding of the Subset Construction to convert an NFA to a DFA (we did an example of that in the lecture).
  • Sep 2: Quiz on DFAs – question 1.6f, pg 84 in Sipser. Closure properties of regular languages: union, concatenation, star; we show how to build a DFA M3 from M1 and M2 so that L(M3) is the union of L(M1) and L(M2). Explained what’s expected from assignment problems, and described the outline of solution of Problem 1.31.
  • Aug 31: review of the hierarchy: alphabet, string/word, language. Practice designing DFAs by doing exercise 1.6; finish all parts of exercise 1.6 by next lecture.
  • Aug 26 lecture: please read chapter 0 on your own, and do the corresponding exercises and problems. We started chapter 1, definition of a DFA and an example. Acceptance of a language by a DFA; definition of regular languages.
  • First lecture on August 24th, at 12pm, in Sierra Hall 1131


  • Assignment 1 (due on September 21): 1.31,36,37,40,41,42
  • Assignment 2 (due on October 5; extended to October 12): 1.39,46,51
  • Assignment 3 (due on October 19): 2.4,6,9,20 — only hand in those for which the book does not provide answers
  • Assignment 4 (due on November 2): 2.25,26,27
  • Assignment 5 (due on November 16): 2.21,33,43
  • Assignment 6 (due on November 30): 2.44,49