Equivalence of Regular Languages and Regular Expressions
Ashwin Lall · Mathematical Foundations of Computer Science · 2024
In this section we will see that the languages accepted by DFAs and NFAs are exactly the same as the languages of regular expressions. This means that we can use these two ideas interchangeably. Moreover, we will prove the equivalence constructively, which means that we will have a way to design a regular expression from any DFA and vice versa.