4.1. Regular Expressions¶
The Regular Expression (also known as RegEx or RE) is another way to define a language. They are used a lot by practicing programmers for things like defining simple search patterns. This adds another way to define languages along with the ones that we already know: Grammars, DFAs and NFAs. Or, we could just describe the language using an English description. Why do we need another one?
The problem with an English description (or any other language that people speak) is that it is too imprecise, and not something that we can easily implement. Using a DFA or NFA typically requires some sort of graphical editor, and it takes a bit of time to enter all the states and transitions. We will see that regular expressions are easy to type, and they tend to use relatively short descriptions for common languages that we want to represent. Of course, even a relatively small and precise specification for a language can be hard to come up with (or to understand). But at least with a regular expression, it is usually quick and easy to type once you have it.
4.1.1. Definition and Examples of Regular Expressions¶
- Definition for Regular Expressions (RE): Given \(\Sigma\),
\(\lambda\), and all \(a \in \Sigma\) are RE
If \(r\) and \(s\) are regular expressions, then
\(r + s\) is a RE
\(r s\) is a RE
\((r)\) is a RE
\(r^*\) is a RE
\(r\) is a RE if and only if it can be derived from (1) with a finite number of applications of (2).
As we will prove soon, regular expressions don’t give us any more power than we already had with DFAs. But they are often easier to write down, as you will see in the following exercises.
