- Strings, languages, and understanding basic operations
on languages (union, intersection, complement, concatenation,
Kleene star)
- Ability to do induction proofs
- Regular languages via recursive/inductive definition
- base cases, closure under finite union and concatenation
- Regular expressions
- ability to generate a regular expression for a given
language decription
- ability to understand regular expressions and explain
the language in English or other formal ways
- Deterministic Finite Automata (DFAs)
- formal definition via graphical notation and tuple notation
- understand δ and δ*
- meaning of the language accepted by a DFA
- ability to design DFAs for a given language
- ability to understand a given DFA and the language it accepts
- product construction of two or more DFAs
- prove following closure properties for languages accepted by DFA:
complement, intersection, union,
and set difference via product construction
- Non-deterministic Finite Automata
- formal definition via graphical notation and tuple notation
- understand δ, δ*, ε-closure
- understand meaning of the language accepted by a NFA
- understand how to check whether a given string is accepted by a given NFA
- ability to design NFAs for a given language
- ability to understand the language accepted by a NFA
- closure properties captured by NFA: union, concatenation, Kleene star
- Thompson construction to create an NFA from a regular expression
- Subset construction to converτ an NFA into an equivalent DFA
Incremental subset construction to generate only the useful states
- Closure properties of regular languages and laguage transformations
- via definition of regular languages (union, intersection, Kleene *) or NFAs
- via DFAs (complement, intersection, union, set difference etc)
- via more avanced constructions using reg exps, DFAs, NFAs and their combination
(examples: PREFIX, SUFFIX, CYCLE insert1, delete1, etc that are in labs, home works)
- Fooling sets and non-regularity
- Distinguishable pair of strings with respect to a language
- Definition of a fooling set
- Understand why a fooling set provides a lower bound on the
number of states in a DFA for a given language
- Proving that a given language is non-regular
via infinite fooling sets or other methods
- Using basic closure properties to prove non-regularity
- Context free languages and grammars
- formal definition of a context free grammar
- formal definition of the derivation of a string in a grammar, and the language defined by a cfg
- ability to design a context free grammar for a given language and explain it
- ability to understand the language of a given simple context free grammar
- basic closure properties of cfls (union, concatenation, Kleena star) and ability to prove these via grammars