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\}\) \(\{\epsilon, good, bad, goodgood, gooodbad, badgood, badbad, goodgoodgood, goodgoodbad, \ldots\}\)

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.