Regular Expressions

03-04-2026

What is a Regular Expression

We know from Finite Automata that there is a way to parse an input string x and to determine its validity through various states and transitions. However, when composing a programming language from a compiler level, the set of words that make up the language is massive. Thus, a concise and robust system is needed to describe valid words. Most systems use Regular Expressions.

There are just a few unique symbols needed to grasp regex:

  • a∗a^*, the Kleene closure. This denotes that the character coming before it occurs 0 or more times.
  • aia^i, the finite closure. This dictates that the character can appear [0,i][0,i] times in a row.
  • a+a^+, the positive closure. This tells the regex that there may exist one or more occurences of the character.
  • \textasciicircumc\textasciicircum c, the complement. This RE tool specifies the set {∑−c\sum - c}

Now, to really build an inpenetrable system, we must have an accurate understanding of how regular expressions mingle with one another. Suppose L(r)L(r) is the language described by RE rr.

  1. Alternation: r∣sr|s is {x∣x∈L(r) or x∈L(s){x | x \in L(r)\space \text{or} \space x \in L(s)}}
  2. Concatenation: rsrs is {xy∣x∈L(r) and y∈L(s)xy | x \in L(r) \text{ and } y \in L(s)}
  3. Closure: r∗r^* is ⋃ri\bigcup r^{i}

More Depth

Regular expressions are a fascinating subset of mathematics and computation. Having been extensively over decades, there are many interesting and useful properties. For example, must RE expressions are closed, meaning that by applying that operation between two REs, the output itself is an RE. An obvious example of this would be if you were to enumerate every single word in a language, model them as an RE, and then join them together as an alternation: a0∣a1∣a2∣a3∣…a_{0}|a_{1}|a_{2}|a_{3}|\dots . This property is pretty simple but is very important in the application of syntactic categories and the implementation of Scanners.