4. 正则表达式的能力¶
既然我们已经知道了正则表达式的定义，并有了一些书写它们的经验， 接下来要做的就是理解它们有多强大。 特别地，一个自然会问的问题是：正则表达式与正则语言之间是什么关系？ 回顾一下，正则语言被定义为任何能被 DFA 接受的（等价地，也是任何能被 NFA 接受的）语言。
在本节中，我们将使用标准的模拟方法来证明正则表达式与正则语言等价。 这里的意思是，一个正则表达式可以转换为正则语言的一种表示（特别是 NFA）。 因此，任何一个正则表达式都表示一个正则语言。 反过来，任何正则语言（以 NFA 的形式）都可以转换为一个正则表达式。 因此，任何正则语言也都可以由一个正则表达式来表示。 于是结论便是：二者等价。
4.1. 每个正则表达式都有等价的 NFA¶
小结： 我们现在已经证明：(1) 由 \(\lambda\) 或字母表中的 单个符号构成的 RE 都可以由一个 NFA 表示；(2) 我们可以把任何 NFA 转换为具有单个最终状态的等价 NFA。 这简化了我们接下来要使用的其余构造。
现在我们完整地写出整个归纳证明。
小结： 通过归纳论证，我们现在已经证明可以把任何 RE 转换为 NFA。 因此，所有 RE 接受的都是正则语言。
4.2. 将正则表达式转换为 NFA¶
4.3. 正则表达式到最小化 DFA 的示例¶
4.4. 将 NFA 转换为正则表达式¶
4.5. 小结¶
我们现在已经证明了以下几点：
任何 RegEx 都可以用 NFA 或 DFA 表示。
任何 NFA（或 DFA）都可以用 RegEx 表示。
因此，所有能由正则表达式表示的语言都是正则语言， 而所有正则语言也都可以用正则表达式来表示。
