math - 带有连接的常规语言

Question

常规语言在操作下关闭：

init(L) = 字符串 w 的集合，使得对于某些 x，wx 在 L 中。

编辑： x 可以是任何字符串、字符或空字符串我如何证明这一点？

Answer 1

好的，第一次看错了问题，现在我明白了。它仍然微不足道。查看自动化，您搜索的是自动化的一部分，分为两个状态集 S1 和 S2，因此它们之间只有一个转换（如果它从 S1->S2 S1 当然包含开始节点，而 S2 是结束节点）。这样总是存在的（空语言除外），如果没有这样的节点你可以添加一个，所以 w 只是一个包含空单词的集合，它当然也是常规的（以及空语言的情况）。

Answer 2

除非我有误解，否则答案是你不能。因为这不是真的。

首先，让我们考虑一下语言L = {aa, bb, cc}和字母表{a, b, c}

所以，init(L) = {a, b, c}。但是， 中的每个元素init(L)都不在L.

编辑：如果我们连接空字符，那么init(L) = {a, b, c, aa, bb, cc}. 这仍然不等于L。

Answer 3

一种语言是正规的，当且仅当存在一个识别它的有限状态自动机。因此，假设 L 是一种常规语言，让 A 是识别它的自动机。现在，如果有一组可能的转换从那里开始并以“接受”状态结束，那么就说 A 的状态是“好的”。定义一个新的自动机 A'，其中所有到“好”状态的转换都被直接转换为接受状态。那么 A' 识别的语言就是 init(L)。

Answer 4

我认为这是一个新的 DFA B，它使 A 的所有状态（原始 DFA）可以达到 A 的最终状态 B 的最终状态。