Regular Languages

1.1

Formal Definition of Finite Automaton

Regular Operation

Union

Concatenation

Star

Non-determinism

Theorem:

Every non-deterministic automaton has an equivalent deterministic automaton

Theorem:

A language is regular if and only if some regular expression describes it.

Pumping lemma for regular languages

Xyz

GNFA—