RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

Finite languages are easy to understand, specify and recognize, but they're not very expressive.

In practice, many useful languages are not limited to a fixed number of strings. As a result, we need some way to begin to represent infinite languages.

Language set operators

To discuss regular languages, we need to first define the following set operators:

1. If R₁ = {s_1,1, s_1,2, ...} and R₂ = {s_2,1, s_2,2, ...} then R = R₁R₂ = {s_1,1s_2,1, s_1,2s_2,1, s_1,1s_2,2, ...}
   1. Informally, the concatenation of two sets involves squishing together the a combination of one element from each set in the provided order of operands
2. If R₁ = {s_1,1, s_1,2, ...} and R₂ = {s_2,1, s_2,2, ...} then R = R₁ ∪ R₂ = {s_1,1, s_2,1, s_1,2, s_2,2, ...}
   1. Informally, the union of two sets involves including any element in either set
3. If R₁ = {s₁, s₂, ...} then R = R₁^* = {ε, s₁, s₂, s₁s₁, s₁s₂, s₂s₁, s₂s₂, s₁s₁s₁, ...}
   1. Informally, the Kleene closure of a set involves starting with ε and concatenating any element of that set any number of times

Definition

Regular language representations

There are two straightfoward ways of specifying a regular language:

• A regular expression
• A finite automaton

These constructions will be explained in detail on subsequent pages.