4.3. The Power of Regular Expressions¶
Now that we know the definition for Regular Expressions and have a bit of experience with writing them, the next order of business is understanding how powerful they are. In particular, a natural question to ask is: What is the relationship between Regular Expressions and Regular Languages? Recall that a Regular Language is defined to be any langauge that can be accepted by a DFA (and equivalently, any language that can be accepted by a NFA).
In this section, we will use our standard approach of simulation to show that Regular Expressions are equivalent to Regular Languages. By this, we mean that a Regular Expression can be converted to a representation for a Regular Language (in particular, a NFA). Therefore, any Regular Expression represents a Regular Language. Going the other way, any Regular Language (in the form of an NFA) can be converted to a Regular Expression. Thus, any Regular Language can be represented by a Reglar Language. The conclusion is then that these are equivalent.
4.3.1. Every Regular Expression has an Equivalent NFA¶
Summary: We have now shown that (1) an RE consisting of \(\lambda\) or of a single symbol from the alphabet can be represented by an NFA, and (2) 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.
Now let’s spell out the entire induction proof.
Theorem 4.3.1
Theorem: Any RE can be converted to an equivalent NFA.
Proof: We will prove this using induction.
Base Case: REs \(\lambda\) and symbols \(a \in \Sigma\) can be all be converted to NFAs as demonstrated by the constructions in Part 1 above.
Induction Hypothesis: When trying to build the NFA equivalent to \(t\) that was created using one of the construction rules \(t = r + s\), \(t = rs\), or \(t = r^*\), we can assume that \(r\) and \(s\) can be converted to NFAs.
Induction Step: By definition, any RE \(t\) must either be a member of the base case or built by one of the three builder rules. If it can be formed using one of the builder rules, then from the induction hypothesis we can assume that \(r\) and \(s\) used to build \(t\) can be converted to equivalent NFAs. From the constructions shown in Parts 1, 2, 3, and 4 above, \(t\) can therefore also be converted to an equivalent NFA.
Summary: Using an inductive argument, we have now demonstrated that we can convert any RE to an NFA. So, all REs accept a regular language.
4.3.5. Summary¶
We have now demonstrated the following:
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.
