RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

We now have a good understanding of finite languages and the basic setup of regular languages via regular expressions.

But how do they relate to eachother?

All finite languages are regular

Let's say we have a finite language L with the following specification:

L = {s₁, s₂, ..., s_n}

We can construct a regular expression for this language as follows:

R = s₁ ∪ s₂ ∪ ... ∪ s_n

This regular expression matches all of the strings in L.

Special case: The empty language

We know that the following regular expression:

R = ø

matches the empty language. This language is both regular and finite because it contains a fixed number of strings.

Finite-ness of a regular expression

Any regular expression that does not contain the Kleene closure operator always represents a finite language.

The concatenation and union operators, when applied to a finite set of symbols, always results in a finite set of strings. Furthermore, the process of enumerating the strings in the language is fairly straightforward.

However, the Kleene closure operator is often used to specify infinite languages. Any non-empty inner expression that has the Kleene closure operator applied to it and then optionally concatenated or combined via union with any other expression will result in an infinite language.

Practically speaking, any Kleene closure operator on anything other than ε or (ⁿε)ⁿ will result in an expression represeting an infinite language.

Conclusion

In conclusion, all finite languages are regular but not all regular languages are finite. Determining whether a regular language is finite and enumerating its strings is fairly straightforward.