4. Regular languages

Regular languages

Each regular expression over some alphabet $S$ represents a language over $S$.

The following are two different things:

• A regular expression $R$. A string or finite pattern.
• The language $R$ represents: $\text{Language\_of}(R)$. A set of words over $S$, words following the pattern.

Regular Language

A regular language is any language that can be representeed by a regular expression. A language $L$ is regular if $L=\text{Language\_of}(R)$ for some regular expression $R$.

Link to original

To compare:

• A regular expression is a pattern.
• A regular language is a set of words following a pattern.

Recursive description

The recursive description of the language $\boxed{\text{Language\_of}(R)}$ represented by the regular expression $R$ is:

• Basis Case: $$\begin{array}{rl}\text{Language\_of}(\varnothing )& =\varnothing \\ \text{Language\_of}(ϵ)& =ϵ\\ \text{Language\_of}(a)& =a\text{ for any symbol }a\text{ in the alphabet }S\end{array}$$
• Recursive Step: If $R$ and $Z$ are regular expression, then:
  • $\text{Language\_of}(R\cup Z)=$ all words that belong either to $\text{Language\_of}(R)$ or to $\text{Language\_of}(Z)$.
  • $\text{Language\_of}(RZ)=$ any words from $\text{Language\_of}(R)$ followed by any word from $\text{Language\_of}(Z)$
  • $\text{Language\_of}(R^{\ast })=$ any word from $\text{Language\_of}(R)$ followed by any word from $\text{Language\_of}(R)$ … (the number of iterations is arbitrary, possibly none)