3:  Automata and grammars


A. Finite-state Machines


  - Basics of FSA's

    o Alphabets, nodes, and arcs

    o The "language" of an FSA

    o Iteration

    o Nondeterminism

    o Combinations of FSA's


  - Exercises on writing an FSA by hand


  - Regular expressions and pattern matching


  - Regular expressions in practice:  'grep'


  - Limits of finite-state automata: long-distance dependencies

    o Theoretical arguments

    o Linguistic arguments

    o Practical considerations



B. Context-free Grammars


  - Derivation of a strings via rewriting


  - Syntactic ambiguity: multiple derivations


  - Left, right, and center-embedding


  - RTN's and the role of recursion