A regular language is a set of strings that can be recognised by a Finite automata.
see Kleene’s Theorem.
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.
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.