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).
4.1.2. Converting a Regular Expression to a NFA¶
Summary: We can convert any NFA to an equivalent NFA with a single final state. This simplifies the rest of the constructions that we will use.
Summary: We can convert any RE to an NFA. So, all REs accept a regular language.
4.1.5. Converting Regular Languages to Regular Expressions¶
4.1.6. Converting Regular Languages to Regular Expressions Example¶
4.1.7. Summary¶
We have now demonstrated several things:
Any RegEx can be represented by an NFA or a DFA.
Any NFA (or DFA) can be represented by a RegEx.
Thus, all languages that can be represented by regular expression are regular, and all regular languages can be represented by a regular expression.
As we noted at the start, 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.
