Basics of Set Theory. Set operations and their properties. The Russell's paradox.
Relations and functions between sets. Count of the number of injective functions on a finite domain. The Birthday problem.
Equivalence relations. Propositional formulae and truth tables. Graphs and Trees.
Proof Techniques: proof by contradiction, induction on integers and structural induction. Examples. Alphabets, Strings and Languages.
Strings. Operations on strings. Languages. Operations on languages. Language generation and recognition. Overview on grammars and automata. Formal definition of grammar. One-step derivation. Many-step derivation. Language generated by a grammar. Examples.
Examples of Languages generated by a grammar. Formal verification that a candidate Grammar generates a given Language. Generalities on Automata. Accepters and Transducers. Formal definition of Deteministic Finite State Automaton (DFSA). Transition Graphs.
Preparation to the Midterm Examination. Exercises on Languages and Grammars.
Review of the Midterm Examination. DFSA: extended transition function. Language recognized by a DFSA.
Definition of Nondeterministic Finite State Automata (NFSA). Extended transition function. Language recognized by an NFSA. Equivalence between NFSA and DFSA: the Subset construction.
Nondeterministic Finite State Automata with epsilon moves. Epsilon closure of a state. Extended transition function. Language recognized by an NFSA with epsilon moves. Equivalence between NFSA with epsilon moves and DFSA: the Generalized Subset construction.
More on equivalence relations. Equivalence relations and set partitions. Quotient set with respect to an equivalence relation. The indistinguishability equivalence relation on the set of states in a DFSA. Minimization of DFSA. Examples.
Congruence relations. Minimization of a DFSA: the quotient automaton. Regular expressions. Languages denoted by regular expressions. Construction of an NFSA with epsilon moves that accepts a language denoted by a given regular expression.
Equivalence between regular languages and languages denoted by regular expressions. Derivation of the regular expression that denotes the language accepted by a given NFSA. Applications: regular expressions in Unix.
Closure properties of Regular Languages. Pumping Lemma.
Review of the Midterm Examination. Exercises on FSA and Regular Languages.
More on the minimization of DFSA. Exercises on the use of the Pumping Lemma.
Context Free grammars and Context Free languages. Parse Trees. Leftmost and rightmost derivations. Ambiguity.
Definition of (nondeterministic) Pushdown Automata (PDA). Acceptance by empty stack or by final state. An example: the language of the palindromes.
Pushdown Automata and Context Free Grammars. Instantaneous descriptions. Deterministic PDA. LL(k) grammars. Presentation of a Top-down predictive parser for mathematical expressions based on an LL(k) grammar (see online package).