home

Regular languages

A regular language is a set of strings that can be recognised by a Finite automata.

see Kleene’s Theorem.

Regular operations

Given two languages on $$\Sigma = \{a, b,\ldots, z\}$$, $$A = \{{good}, {bad}\}$$ and $$B = \{{boy},{girl}\}$$.

Term Notation Operation Example
Union $$A \cup B$$ $$\{x \vert x \in A \text{ or } x \in B\}$$ {good, bad, boy, girl}
Concatenation $$A \circ B$$ $$\{xy \vert x \in A \text{ and } y \in B\}$$ {goodboy, goodgirl, badboy, badgirl}
Kleene star $$A^*$$ $$\{x_1x_2 \ldots x_k \vert k \ge 0 \text{ and each } x_i \in A\}$$ {ε, good, bad, goodgood, gooodbad, badgood, badbad, goodgoodgood, goodgoodbad, …}

Languages remain closed under all the above operations.

Groups of these operations may the be used to define Regular expressions that define complex languages.

Proving non-regularity

The closure property may be used to prove a language is non-regular by assuming it to be regular, transforming a definition into a known non-regular form, then showing by contradiction that the original regularity assumption does not hold.

Alternatively, the Pumping lemma may be used.