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, especially by programmers for 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 requires typically requires some sort of graphical editor, and this takes a bit of time to enter. We will see that regular expressions are easy to just type, and they tend to be relatively short descriptions for common languages that we want to represent. Of course, even a relatively small 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 \(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 will be a useful first step.
Summary: We can convert any RE to an NFA. So, all REs are associated with a regular language.
