regular-language - 如果 pref(L) 是正则的，这是否意味着 L 也是正则的？

Question

我有这个家庭作业练习：

假设我们有一种语言 L。我们知道该语言pref(L)（ 的所有前缀L，包括L本身的所有单词）是一种常规语言。这是否意味着该语言L也是常规的？

我采用 NFApref(L)并将其（通过从 的 2 个 epsilon 转换q0）划分为 2 个单独的 NFA，分别为 1 个定义L和另一个定义pref(L)\L。

我实际上得到的是 NFA L，这意味着它是常规的。

我不确定这是正确的方式或是否合法。我很高兴有另一个线索。

提前致谢，

亚龙。

Answer 1

如果 pref(L) 是正则的，那么 L 也不一定是正则的。

例如，让 Σ = {a} 是一元字母表。我将声称如果 L 是Σ 上的任何无限语言，那么 pref(L) = Σ*。要看到这一点，首先要注意 pref(L) ⊆ Σ*，因为每个 pref(L) 都是 Σ 上的语言。现在，考虑 Σ* 中的任何字符串，其形式必须为 a ⁿ。如果 L 是 Σ 上的无限语言，它必须包含至少一个形式为 a ^m的字符串，其中 m ≥ n。那么 a ⁿ将是 a ^m的前缀，所以 a ⁿ ∈ pref(L)。这表明 Σ* ⊆ pref(L) 并且 pref(L) ⊆ Σ*，所以在这种情况下 Σ* = pref(L)。

现在，我们需要做的就是在 Σ = {a} 上找到一个非常规语言。例如，以语言 { a ^{2 n} | n ∈ N } 所有长度为 2 的幂的字符串。可以使用 Myhill-Nerode 定理或抽水引理证明这种语言不规则。但是，通过上述结果，我们知道 pref(L) 是一种正则语言。

希望这可以帮助！