正则表达式转 NFA
定理: 如果 \(R\) 是正则表达式且 \(A = L(R)\), 则 \(A\) 是正则语言.
证明
将 \(R\) 转换为等效的 NFA \(M\).
正则表达式由 \(\Sigma\) 构成, 并通过正则操作组合得到. - 正则表达式
在NFA_转_DFA 的闭包属性部分, 描述了如何通过 NFA 来表示正则操作, 即正则操作转换为 NFA 的方式.
下面是特定语言转换为 NFA 的方式:
结合上述两种方法, 即可将正则表达式转换为 NFA.
例子
将 \((a \cup ab)^*\) 转换为等效的 NFA:
