Language concepts
formal vs. natural; formal lang.=alphabet+set of words;
methods of specifying; Kleene star closure, null word

Recursive definitions
3-rule approach: base elements, building rule(s), complete

Regular expressions (RE)
building operations (letter, +, *, concat.); distributive law;
set operations on languages & relation to RE operations

Finite automata (FA)
definition (states, alphabet, transitions + deterministic & complete);
representations: rule list, transition table/diagram; language def.

Transition graphs (TG)
definition; like & different from FA (any length string on transitions,
multiple start states, can crash, non-determinism allowed = alt. paths)

Kleene's theorem
equivalence of FA, TG, RE; three-part proof; process to convert TG to RE;
FA construction rules for RE operations; NFAs & non-determinism

Finite automata with output
difference from FA (no final state, output); Moore & Mealy
machines; equivalence; modeling sequential circuits

Regular languages
definition; set operations producing regular languages: union, set product,
Kleene star (concatenation closure), complement, intersection; proofs

Non-regular languages
definition; examples; the Pumping Lemma, Myhill-Nerode theorem, using them

Decidability
effectively solvable, decision procedure, decidability;
questions: empty? finite? equivalent languages?; methods