CSc 481/681 Automata
Winter Quarter 1998 (Computer Number: 1585/1593)
5.30 to 7.00 MWF, 105-CS

Pre-requisites: CSc 431/631.
Text: Automata and Formal Languages, An Introduction by Dean Kelley, Prentice Hall (1995).
Course Description: Theory of formal languages and the computing devices that recognize them. We shall study three classes of formal languages: regular languages, context-free languages and non-context-free languages. For each class, we shall study the corresponding computing device (finite automata for regular languages, pushdown automata for context-free languages and Turing machines for non-context-free languages). We shall also look at some applications in computing for each of the classes of languages.

Grading Policy: The grading for this course will be based upon the following components: components:

1. Exam 1 worth 25% (tentative date: 30 January).
2. Exam 2 worth 25% (at the end of the quarter).
3. Several homework assignments, assigned on Mondays and to be turned in the following Monday, worth 25%.
4. Several surprise quizzes worth 25%.

Additional Requirement for graduate credit: To earn graduate credit, the student will be assigned additional problems in the homework assignments.

The final letter grade will be determined based on the following criteria:

Last date to withdraw: 6 February, 1998.

Tentative Schedule:

Jan. 5    Overview, (1.1) Alphabet, Words, Languages
                    (1.2) Operations on strings
                    (1.3) Operations on languages
     7    (2.1, 2.2) Regular languages and expressions
     9    (2.3, 2.4) Deterministic Finite Automata (DFA)

    12    (2.5) Non-deterministic Finite Automata (NFA)
    14    (2.6) Equivalence of DFA and NFA
    16    (2.7) NFAs with empty-transitions

    19          HOLIDAY
    21    (2.8) Equivalence of Regular Expressions and DFA/NFA
    23    (2.9) Properties of regular languages

    26    (2.9) Pumping Lemma
    28    (2.10) Applications
    30    EXAM1

Feb. 2    (3.1, 3.2) Regular grammars 
     4    (3.3) Context-free grammars (CFG)
     6    (3.4) Parse trees, Ambiguity

     9    (3.5) Simplification of CFGs
    11    (3.6) Properties of CFLs
    13    (3.6) Properties of CFLs

    16    (3.7) Pushdown automata (PDA)
    18    (3.7, 3.8) PDAs continued, Equivalence of PDA and CFGs
    20    (3.8) Equivalence of PDAs and CFGs continued

    23    (4.1) Turing Machines (TM)
    25    (4.2) TMs as language acceptors
    27    (4.3) TM construction

Mar. 2    (4.4, 4.5) Variations of TMs, Universal TM
     4    (5.1) Languages accepted by TMs
     6    (5.2, 5.3) Recursive and Recursively enumerable languages

     9    Review