regular-language - 正则语言的并集是正则的吗？

Question

如果语言 L1,...,Ln 是正则的，那么它们的并集也是正则的吗？

我们知道两种正则语言的并集是正则语言。如何证明多个正则语言的并集也是正则的？

Answer 1

您可以使用归纳法。这是一个非常非常生锈的证明草图。

鉴于 -

两种正则语言的并集是正则的。

令 f(n) 为表示 n 个正则语言的并集的函数。

问题f(n) 是常规语言吗？

基本案例 -

如果 n = 1，则单个正则语言的并集是正则的。

如果n = 2，那么根据给定的假设，我们知道f(2)是正则的。

归纳假设-

假设对于所有 n <= k，f(n) 是正则的。

归纳步骤 -

设 n = k+1。通过归纳假设我们知道 f(k) 是正则语言。所以 。 。 .

f(n) = f(k+1) = Lk+1 U f(k)

其中Lk+1是第k+1个正则语言。由于 f(k) 和 Lk+1 是正则的，因此根据给定的假设，f(n) = f(k+1) 是正则的。

QED

有关归纳证明的更多信息

维基 - http://en.wikipedia.org/wiki/Mathematical_induction

可汗学院 - https://www.khanacademy.org/math/precalculus/seq_induction/proof_by_induction/v/proof-by-induction