这语言为什么是常规语言？

Question

在一本书中遇到了这一点，我想知道为什么以下语言是常规的？

$$ l={a ^ nww ^ r：n \ geqslant 0，w \ in \ {a，b \} ^ 3 \} $$

说 $$ \ {a ^ n：n \ geqslant 0 \} $$ 是一种常规语言，因为它可以由a表示正则表达式 $$ a * $$ ， $$ \ {ww ^ r：w \ in \ {a，b\} ^ 3 \} $$ 是一种常规语言，因为它是有限的;因此，两种常规语言的联盟常规语言？

Answer 1

这是 not 两个常规语言的联盟！这是一个 condenation 。注意差异，

1. 联盟： $ l_1 \ cup l_2 $
2. 连接： $ \ {ab：a \ in l_1 \ wedge b \中的l_2 \} $ 。

表示，您的其他观察是正确的，并且实际上，两种常规语言的串联也是普通的。您可以通过为常规语言构建两个NFA来证明这一点，并将 $ l_1 $ 连接到的启动状态>$ l_2 $ 由 $ \ epsilon $ -transition。