1

我需要帮助解决我在计算课程模型中遇到的几个硬件问题。我阅读了文本中的相关章节（Michael Sipser's Introduction to the Theory of Computation），但我觉得这些硬件问题需要这本书没有给我的知识......第一个问题是：

(1) 证明不存在这样的语言 L 使得 L* = {a}* {b}* 提示是使用矛盾。

显然右边是正则表达式；零个或多个 a 后跟零个或多个 b。这也可能是空字符串 epsilon。

我的麻烦来自于 L*。由于语言 L 上的 *，我完全不知道应用于语言的 * 是什么，或者如何使用这个等式。

对此问题的任何帮助或资源将不胜感激。

=====

第二个问题比较简单，感觉差不多可以了。我可以为自己辩护，所以我想问题是正式写出来。第二个问题是这样的：

(2) 证明如果 A 和 V 是相同字母表 (sigma) 上的语言并且 A（是 B 的子集），那么 A*（是 B* 的子集）。提示是使用归纳法。

现在显然（例如）如果 sigma = {1, 0}

A = {00, 01, 10, 11}

B = {00, 01, 10, 11, 100, 101, 110, 111}

然后 A* 中的任何内容都在 B* 下关闭，因为 B = A + 其他一些东西......如果有人可以帮助我将其形式化为归纳形式，我将不胜感激。

谢谢

4

1 回答 1

1

(1) 这是一个有用的递归定义L*：

  1. epsilon 在L*
  2. 如果x在L,x在L*
  3. 如果x并且y在 中L*，那么xy
  4. L*是满足 1. - 3. 对于给定的最小语言L

给定这个定义，这里有一个矛盾的证明：假设R* = a*b*. 然后ab是在R*。由 3.,abab也必须在R*. 但是R* != a*b*，一个矛盾。所以R* = a*b*一定是假的；换句话说，因为没有语言R是R* = a*b*.

直觉很简单：L*是所有字符串的语言，可以通过连接零个或多个（允许重复）字符串从L. 递归定义的工作原理是允许零个字符串（在 1. 中）、从L（在 2. 中）恰好取一个字符串的字符串以及通过连接可能来自L（在 3. 中）的许多字符串而形成的字符串。

(2) 使用我上面给出的定义，我们对 中的连接字符串的数量进行归纳处理A*。对于 0 连接，空字符串在A*andB*中，所以我们很好（参见规则 1.）。对于 1 个连接，因为A是 的子集B，所以 in 的字符串A将在A*（参见规则 2），并且 stringsfromB将在B*（相同的规则），因此所有采用一个连接的字符串A*也在B*. 现在，假设所有在 in 中进行k连接的字符串A*也在B*. 接受k+1串联的字符串A*呢？好吧，这些是使用规则 3 形成的。在字符串上并且x严格小于yA*k+1级联，即至多k级联。换句话说，任何A*采用k+1串联的字符串都可以重写为xy, where xand yare in A*, and xandy最多采用k串联。由于所有A*最多k连接的字符串也都在B*（根据我们的假设），我们有它x并且y在 B* 中。根据规则 3.，xy也必须在B*. 因此，k+1串接 in 的字符串A*也必须属于B*. 这样就完成了证明。

注意：这掩盖了一些细节并且不是很正式，但你应该明白这个想法并希望能够塑造它。如果您需要比这更精致的东西，请告诉我，我可以尝试与您合作。

于 2012-06-25T23:32:16.860 回答