Lecture by Professor Ajith Abraham (slides)
- Why study automata theory
- 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
-
deductive proofs
-
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
-
expressions
-
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
-
constructing regular expressions and associated languages
-
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)
-
context-free grammars
-
Pushdown automata
-
definition of pushdown automaton
- pushdown automaton as a combination of a non-deterministic automaton and a pushdown stack
- operations of pushdown automaton
- formal definition
- graphical notation
-
definition of pushdown automaton
Reading assignment: pages iii-224