表明，对于任何语言L1和L2，我们有（1）。 L1L1 ^ * = L1 ^ * L1L1 ^ * [关闭]

Question

我正在学习自动机理论和形式语言，并对如何从我的硬件计算＃3感到困惑。以下提供了与HW的链接：https://www.eecs.wsu.edu/~zdang/c317/Assignments/homework1.pdf

对于3.1我知道L1L1 ^ *基本上与说^ ^ * L1L1 ^ *相同，但不知道如何表达它。如果我将两边除以L1，我能说，L1 ^ * = L1 ^ * L1 ^ *因此L1 ^ * = L1 ^ *？

对于3.2，我们给出方程（L1 ^ * L2）^ * =（L1 + L2）^ *。为了证明右侧，我知道我们可以将L1 ^ *跟随L2一遍又一遍地使其与左侧相同。我再也不确定如何表达这一点。

任何帮助将不胜感激。

Answer 1

要显示L1L1 * = L1 * L1L1 *，我们需要显示L1L1 *包含L1 * L1L1 *中的所有内容，反之亦然。

• L1L1 *包含L1 * L1L1 *中的所有内容。对于所有非负整数a和b，后者在L1 ^ aL1L1 ^ b中包含字符串。通过连接的相关性，我们可以将L1 ^ aL1L1 ^ b重写为L1L1 ^（a + b），其必须在L1L1 *中。
• L1 * L1L1 *包含L1L1 *中的所有内容。后者包含L1L1 ^ b中的字符串。通过求幂零，我们得到L1 ^ 0 = {空字符串}，并且通过语言连接和字符串连接与空字符串，我们可以看到L1 ^ 0L1L1 ^ b = L1L1 ^ b。但是，通过选择重复第一L1 *零次，L1 ^ 0L1L1 ^ b在L1 * L1L1 *中。

（L1 * L2）* =（L1 + L2）*是不正确的。要看到这一点，请注意后者包含L1中的所有内容，而后者则不包含（对于非平凡的L2）。也就是说，L1可以通过重复一次然后选择L1而从后者获得，但是为了从前者获得任何L1，我们必须重复至少一次，这迫使至少一个L2。