The Power of Finite Memory: Regular Languages

Define deterministic finite automata (DFA) formally and trace the computation of an input string.

Define nondeterministic finite automata (NFA) and trace the computation of an input string.

Prove the equivalence of DFAs and NFAs by converting an NFA to an equivalent DFA using subset construction.

Define regular expressions and write expressions for given language descriptions.

Establish the equivalence of regular expressions and finite automata by converting between them.

Apply the pumping lemma for regular languages to prove that a given language is not regular.

Define and prove closure properties of regular languages (union, concatenation, Kleene star, intersection, complement).

Explain how regular expressions and finite automata are applied in lexical analysis, text search, and input validation.