CSC444/344: Syllabus

This course covers two basic models of computation: finite automata and pushdown automata. We will discuss the various forms that these models can take, the equivalence or inequivalence of each type of model, and the problems that can or cannot be solved by each model.

The topics covered will include:

• Introduction: Motivation, mathematical preliminaries.
• Finite automata: Deterministic finite automata, nondeterministic finite automata, regular expressions, nonregular languages, algorithms for finite automata, state minimization.
• Context-free languages: Context-free grammars, pushdown automata, languages and automata, languages that are not context-free, determinism.

If we have time, I would like to cover some additional topics, at least superficially (in order of decreasing priority):

• Using Regular Expression in programming.
• Using Finite and Pushdown Automata in programming.
• Applications: circuit design, embedded systems, user interfaces, security, etc.
• Automata for reactive systems: Mealy and Moore Machines, UML Statecharts, Input/Output Automata, Process Algebras.
• Other automata: Cellular Automata, Buchi Automata.
• Advanced notions of equivalence of automata: testing, bisimilarity.
• Temporal logics.

By the end of this course you should:

• Be well prepared for CSC544 and several other advanced classes, such as:
  • CSC448 Compiler Design (which uses both REs and CFGs)
  • CSC535 Semantics of Programming Languages (which provides an alternative view of the same subject)
  • SE431 Formal Software Specification and Development (which studies formal logics)
  • SE533 Software Validation and Verification (which uses automata)
  • SE547 Foundations of Computer Security (which uses automata)
• Have a deep understanding of basic formal models of batch computation (Finite and Pushdown Automata).
• Have a deep understanding of basic formal languages (Regular and Context-Free Languages).
• Be able to state and prove fundamental properties of DFAs, NFAs, PDAs, RLs and CFLs.
• Be able to use Regular Expressions and Context-Free Grammars in programming.
• Be able to use Finite and Pushdown Automata in programming.
• Know where to find more information on basic models of reactive computation: Mealy and Moore Machines, Statecharts, and Process Algebras.
• Have an appreciation for the subtlety of non-determism.

The following lecture plan is tentative and subject to change as the course progresses.

• Class 1: [2004/09/08] Sets, Languages, Logic
• Class 2: [2004/09/15] Finite Automata
• Class 3: [2004/09/22] Regular Expressions and Languages
• Class 4: [2004/09/29] Minimal Deterministic Automata
• Class 5: [2004/10/06] Midterm Exam
• Class 6: [2004/10/13] Context Free Languages
• Class 7: [2004/10/20] Non-Context Free Languages
• Class 8: [2004/10/27] Pushdown Automata
• Class 9: [2004/10/03] Buchi Automata
• Class 10: [2004/11/10] Reactive Automata: Mealy, Moore, Statecharts, and Process Algebras
• Class 11: [2004/11/17] Final exam

Lecture slides will be available after each lecture. They will not normally be available before the lecture.

For undergraduates: MAT141 and CSC211. For graduates: CSC415.

You should be comfortable with basic set theory, functions, proofs by induction, basic graph theory, the analysis of algorithms and asymptotic notation (big-oh, theta, omega).

See file:links-main.

Required: Introduction to the Theory of Computation [Amazon, AddAll], by Michael Sipser (PWS, 1997)

It is important that you read the required material before class, and review it again afterwards.

Our goal is to achieve a depth of understanding. It is essential that you understand both examples and proofs.

The midterm exam will be held 2004/10/06 in class. The final exam will be held 2004/11/17 in class.

Block out these dates now!

I will be giving weekly homeworks and having one or two students answer questions in each class, so some attendance will be necessary.

If you are absent from class you are responsible for understanding the material and for finding out about any announcements made in that class. In addition, much of the discussion will be based upon diagrams drawn on the board. They may not appear in the slides and may not be captured well by COL.

There will be weekly assignments, a midterm, and a final. The course grade will be computed as follows:

• Homework and participation: 10%
• Midterm exam: 45%
• Final exam: 45%

You must hand in the homework each week in order to receive the 10 points for homework. Note, however, that I will only review homework in detail for students whose final score is borderline (say between an A- and a B+).

The midterm and final will be cumulative. You must earn a passing grade on the midterm and final to pass the course.

There will be no make-up exams nor extra credit assignments. If there is an extreme emergency and you must miss an exam, you must notify me in advance and provide documented evidence of the emergency.

Students in the distance learning section of the course are expected to take both exams at the same time as the on-campus section of the course. If there is not sufficient space in the regular classroom to accommodate all students, another location will be provided for distance learning students.

Unless otherwise stated, homework assignments are due by 5:30PM before class the week after they are assigned. Any assignment handed in after the deadline will be considered late. Assignments that are late will lose 50% of the points for each day that they are late. No assignment will be accepted more than two days after its due date (including Saturdays, Sundays, and holidays). Assignment deadlines will be strictly enforced; however, your lowest homework score will be dropped in the calculation of your final grade.

Homework assignments must be submitted through the online system. Email submissions will not be accepted.

Distance learning students are subject to the same homework deadlines as students in the regular section of the course.

Program submissions will be assessed on whether they achieve the set task and the quality of the code.

DePaul's academic integrity policy