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.
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.2. Converting a Regular Expression to a NFA¶
4.3.3. Regular Expression to Minimized DFA Example¶
4.3.4. Converting NFAs to Regular Expressions¶
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.
