Finite-State Automata

• Grammars, the languages they can generate, and automata
• Regular grammars: left side - a single non-terminal symbol; right side - a single terminal symbol or a single terminal followed by a non-terminal symbol (or vice versa)
• Finite-state automata, transition networks: states (initial, terminal), arcs/transitions (labeled with element or category names or JUMP)
• A simple example

  NP -> Det NP1
  NP -> NP1
  NP1 -> Adj NP1
  NP1 -> N
  

[L645 Syllabus]