CS 5313 Formal Language Theory

Material covered:

• Why study automata theory and formal languages
• Simple automaton
• Related representations
• Decidability vs. tractability
• Formal proofs
  • deductive proofs
    • proofs about sets
    • proofs involving contrapositive
    • proofs by contradiction
    • counterexamples and their role
  • inductive proofs
    • induction on integers
    • multistep induction
    • structural induction
    • mutual induction
• Basic concepts in automata theory
  • alphabet
  • string
  • language
  • problem --> how to decide if a given string is in a given language
• Finite automata
  • sample finite automaton described and analyzed
  • definition of a Deterministic Finite Automaton (DFA)
  • DFA processing strings
  • other notations for DFA's
    • transition diagrams
    • transition tables
  • extension of the transition function to strings
  • language of the DFA
  • definition of a Nondeterministic Finite Automaton (NFA)
  • extended transition function for the NFA
  • the language of the NFA
  • equivalence of DFA and NFA
    • how to construct a DFA from an NFA
    • subset construction - the good the bad and the ugly
  • applications:
    • NFA in text search
    • DFA in text search
  • finite automata with epsilon-transitions (ε-NFA)
    • uses of ε transitions
    • definition of ε-NFA
    • ε-closures and their role
    • extended transitions for ε-NFA's
    • elimination of ε-transitions
• Regular expressions and languages
  • constructing regular expressions and associated languages
    • expressions
      • symbols
      • "addition" operation
      • "multiplication" operation
      • "closure" operation
      • parenthesis
    • languages and operations
      • union
      • concatenations
      • closures
    • relationship between expressions and operations on them and languages and operations on them as a "definition" of regular expressions
    • precedence of operators and role of parenthesis
  • finite automata and regular expressions
    • schematics interelations between proofs (Figure 3.1)
    • from the DFA to the regular expression
    • proof of Theorem 3.4 as a construction algorithm (Example 3.5)
    • elimination of states as another method for construction of regular expressions from DFA's
    • from regular expressions to finite automata
  • applications of regular expressions
    • regular expressions in Unix
    • lexical analysis
    • finding patterns in textx (for instance WWW pages)
  • regular expressions as algebraic structures; or: all fun things you can do with regular epxressions when you forget that you are a computer scientist
• Properties of Regular Languages
  • introducing languages that are not regular
  • the Pumping Lemma and the basis for recognizing languages that are not regular
  • closure properties of regular laguages; or: all fun things you can do with regular languages when you forget that you are a computer scientist
  • decision properties
    • converting among representations
    • when a language is empty?
    • is a string in a language
  • minimal automata
    • when two states are equivalent?
    • when two languages are equivalent?
    • how to minimize a DFA?
    • why a DFA minimized using the table-filling approach is "the best"?
• Context-Free Grammars and Languages
  • context-free grammars
    • definition
    • derivations
    • language of a grammar
  • parse trees
    • constructing parse trees
    • yield of a parse tree
    • equivalence of five forms of "descriptions" of context-free grammars
  • applications of context-free grammars
    • parsers
    • markup languages (HTML, XML)
  • ambiguity in context-free grammars and languages
    • ambiguous grammars
    • removing ambiguity (but there is no free lunch!)
    • inherent ambiguinty (when two is too much)
• 
  Reading assignment: pages iii-217