SE4I03 Course Outline

1. Finite Automata (finite number of states, and no memory)
   -deterministic finite automata (DFA) 
   -nondeterministic finite automata (NFA) (given any state and an input, 
    there may be more than one choice for the next state)
   -nondeterministic finite automata with epsilon transitions 
    (epsilon-NFA) (just as the NFAs, but "spontaneous 
    transitions are also possible; that is, given a state, we may move
    on an epsilon transition to a new state, on no input)
   -regular languages 
   -DFAs, NFAs, and epsilon-NFAs, recognize the same classes of languages;
    that is, whatever can be computed with one of them, can be computed with
    the others
   -Pumping Lemma for showing that certain languages
    are not regular (in general, showing that a problem
    cannot be solved with a given model of computation, 
    or within a given complexity class, is very difficult,
    so the Pumping Lemma is nice, as it is a simple and easy
    to use tool for proving that particular languages cannot
    be decided with finite automata).

2. Regular Expressions
   -building regular expressions
   -converting DFAs to regular expressions 
   -converting regular expressions to epsilon-NFS
    (thus finite automata and regular expressions are equivalent)
   -regular expressions in UNIX 
   -algebraic rules for regular expressions
   -closure properties of regular expressions 
    (complements, intersections, unions)
   -testing emptiness and membership in regular expressions
    (this is undecidable for Turing Machines, but decidable
    for regular expressions)
   -equivalence of automata 
    (algorithm for showing that two DFAs are equivalent)
   -minimal automata
    (algorithm for producing a minimal DFA equivalent to a 
    given DFA)

3. Context-Free Grammars
   -derivations
    (show that a given string is described by a given CFG)
   -left-most and right-most derivation
   -parse trees
   -trees and derivations
   -YACC parser generator
    (also mention XML)
   -ambiguity
   
4. Pushdown Automata (like finite automata, except they have a stack, 
   with no limit on how much can be stored in the stack)
   -equivalence of PDA and CFG
   -PDA with two stacks are equivalent to general computers
    PDA with finite stack are equivalent to finite automata 

5. Turing Machines (TM) (simplified model of a general computer, but
   equivalent to general computers)
   -Design of TM
   -encoding a TM as a string of symbols
   -languages vs problems (i.e., they are the same thing)
   -Church-Turing thesis
    (all algorithms can be simulated on TMs)
   -Robustness (all variants of TMs are equivalent)
    (many tapes, tapes infinite in one direction only)
   -Decidable, Undecidable, and Semi-decidable languages
   -Halting Problem (can we design an algorithm, which given a TM and an
    input to that TM, decides if the TM will halt; answer: NO) 
   -Diagonalization (a method for showing that the Halting Problem
    is not decidable)
   -Enumerable languages, are languages whose elements can be listed 
    (enumerable languages are not necessarily decidable languages, since
    at any giving point in the listing of the elements, we do not know if 
    the element we are waiting for is not on the list, or simply has not
    appeared yet).  Enumerable languages are equivalent to semi-decidable
    languages.

6. Rudimentary Complexity
   -Feasibility Thesis
    (TMs are reasonable model of computation; a polytime program
    on a RAM machine requires polynomially many steps on a TM)
   -the class P, the class NP
    (P: problems which can be solved in polytime, and therefore, feasibly.  
     NP: problems whose solutions can be verified feasibly)
   -the P vs NP problem, relation to feasibility,
    and relation to cryptography
    (cryptography secure if P not= NP)
   -P vs NP: verifying vs computing
   -NP-completeness (if SAT is in P, P=NP)
   -some reducibility (all NP-complete problems are really SAT in
    disguise)