Regular expressions, DFAs, and NFAs all recognize the same class of languages. This is because we can perform the following conversions:
- Thompson’s construction: Regular expressions to NFAs
- removing epsilon-transitions from NFAs
- subset construction: NFAs without
-transition to DFAs - GNFA: DFAs to regexes