正则表达式

若语言 $A$ 为 正则语言, 则 $A$ 可用正则表达式描述.

构建广义 NFA, 其中转移箭头可以用任何正则表达式作为标号, 一个一个去掉中间状态, 即可得到正则表达式.