0

令 L = {一个n | n >= 0}，其中在此处输入图像描述所有在此处输入图像描述n >= 1。

因此 L 由所有长度的 a 序列组成，包括长度为 0 的序列。设 L2 是 L 的任何无限子集。我需要证明总是存在一个 DFA 来识别 (L2)*。

如果 L2 是有限子集，则非常明显，因为 L2 将是 DFA，因此通过克莱恩闭包，L2* 将被 DFA 识别。但是我无法为无限子集得到它，因为 L2 可能不会表示为 DFA，例如字符串的长度是素数。

4

1 回答 1

1

方法

虽然存在一个 DFA 来描述所有字符串 a n , n >= 0 的集合 L，但不能保证 L 的所有子集都存在 DFA。L 的子集包含所有长度为素数的字符串，如您已经提到，是一个例子，其中描述语言的 DFA 不存在。

正确的方法是直接证明 (L')* 是 L 的任何子集 L' 的常规语言。

定义

让我们定义 GCD(K) = GCD w ∈ K, |w| > 0 (|w|)，其中 K 是 L 的任何非空子集。我们现在可以将语言 K 中所有非空词的所有长度的最大公约数称为 GCD(K)。该定义适用于L 的有限子集和无限子集。

类似地，我们可以定义 LCM(K) = LCM w ∈ K, |w| > 0 (|w|)，其中 K 是 L 的任意非空 有限 子集。

证明

我们将尝试证明当 GCD(L') = 1 时，存在一个数 M 使得所有字符串 a n , n >= M 都属于语言 (L')*。这导致 (L')* 成为正则语言，因为我们可以构造如下形式的正则表达式：

长度小于 M 且属于 (L')*的所有字符串
或
长度大于或等于 M 的所有字符串

上面的正则表达式有一个对应的 DFA，它有 M + 1 个状态。

当 GCD(L') > 1 时，我们可以通过将子集 L' 中的所有单词除以 GCD(L') 将问题简化为 GCD = 1 的情况。

如果 GCD(L') = 1（集合互质），则存在 L' 的有限子集 S，其中 S 中所有字符串的长度的 GCD 也为 1。

我们可以通过构造来证明上述主张。

  • 从 L' 中选取任意元素 w 1 ，|w 1 | > 0 并构造集合 S 1 = {w 1 }
  • 如果 GCD(S n ) = 1，则 S n是我们想要找到的集合。
  • 如果 GCD(S n ) > 1，则从 L'中选取一个元素 w n+1并构造集合 S n+1 = {w n+1 } ∪ S n，使得
    GCD(S n+1 ) < GCD(S n )

如果 GCD(S n ) > 1，则集合 L' 中总是存在一个元素，当我们将它添加到集合时，它会减小 GCD；否则，集合 L' 的 GCD 不能为 1。由于第一个元素 w 1的长度具有有限个因子，所以最终集合 S 的大小是有限的。

回到问题，对于L的任意子集L'，我们可以找到L'的有限子集S，满足GCD(L') = GCD(S)。从集合 S，我们可以用 |S| 构造一个广义线性丢番图方程。未知数我：

1 | w 1 | + a 2 |w 2 | + ... + 一个|S| |w |S| | = c 其中 c 是非负整数

由于 GCD(S) = 1，上面的方程总是可解的，通过递归地将解应用于线性丢番图方程 ax + by = c 的最简单形式。

求解上面 c = 0 到 (LCM(S) - 1) 的广义丢番图方程。解（a 1 , a 2 , ..., a |S|）可以包含负数。但是，我们可以继续在方程两边添加 LCM(S) 的倍数，直到所有解只包含非负数。

令 k 为 LCM(S) 的最小倍数，以便 c = k * LCM(S) + q, q = 0 到 (LCM(S) - 1) 的所有丢番图方程具有非负解。然后我们可以将 M 定义为 k * LCM(S)，因为任何长度大于 M 的字符串都可以分解为 S 中的单词连接（因此在 L' 中）。

基于证明的示例计算

假设 L' 是 L 中长度为素数的所有字符串的集合。

让我们构造集合 S = {a 2 , a 5 }。S 可以是 {a 2 , a 19 } 或 {a 5 , a 23 }，并不重要。M 的最终值可能不同，但不影响 (L')* 是常规语言这一事实​​。

我们需要解 10 个方程（分别）：

2a 1 + 5a 2 = 0 => (a 1 , a 2 ) = (0, 0)
2a 1 + 5a 2 = 1 => (a 1 , a 2 ) = (3, -1)
2a 1 + 5a 2 = 2 => (a 1 , a 2 ) = (1, 0)
2a 1 + 5a 2 = 3 => (a 1 , a 2 ) = (-1, 1)
2a 1 + 5a 2 = 4 => ( a 1 , a 2 ) = (2, 0)
2a 1 + 5a 2 = 5 => (a 1, a 2 ) = (0, 1)
2a 1 + 5a 2 = 6 => (a 1 , a 2 ) = (3, 0)
2a 1 + 5a 2 = 7 => (a 1 , a 2 ) = ( 1, 1)
2a 1 + 5a 2 = 8 => (a 1 , a 2 ) = (4, 0)
2a 1 + 5a 2 = 9 => (a 1 , a 2 ) = (2, 1)

加一个 LCM(2,5) = 10。注意，由于 LCM 的性质，我们可以直接修改解而无需再次求解：

2a 1 + (5a 2 + 10) = 1 + 10 => (a 1 , a 2 ) = (3, 1)
(2a 1 + 10) + 5a 2 = 3 + 10 => (a 1 , a 2 ) = (4, 1)

由于所有解都是非负的，我们只添加一个 LCM(2,5)，M = 10。

(L')* 的正则表达式可以构造为：

a 2 +a 4 +a 5 +a 6 +a 7 +a 8 +a 9 +a 10 a*

正则表达式不是很紧凑，但这不是我们关心的问题。为了证明的目的，我们只需要知道存在一个数 M 使得对于所有 n >= M，一个n属于 (L')*，这意味着存在有限数量的状态并且可以构造一个 DFA .

于 2014-02-19T10:18:01.503 回答