regular-language - 抽引引理(普通语言)

Question

我需要解决抽奖引理问题。

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) }

这是我到目前为止所得到的:

y = uvw is the string from the pumping lemma.

我让y = abbc ^ n，n是抽水引理的长度。 y在L中，因为a:s的数量小于b:s的数量，b:s的数量小于c:s的数量。

我让u = a，v = bb和w = c ^ n。 | uv |

y = abbbbc^n which violates the rule #b(L) < #c(L).

这是正确的吗 ？我在“正确的道路”上吗？

谢谢

Answer 1

抽水式引理的主要思想是告诉您，当您使用具有无限数量术语的常规语言L时，该语言中会有一种模式会永远重复。
与该语言关联的正则表达式将包含KLEENE-STAR(pattern)。
与该正则表达式(和语言)关联的自动机将包含一个循环。
证明是使用鸽子原理完成的。
这很有启发性。
请注意，在这种情况下，所有项都必须以q0开头，以qn结尾。因此，定义语言的自动机是有限的(最多N个状态)，因此状态数量有限，但是单词(即术语)可以具有> N个字母。 pigeon principle告诉我们必须存在一个达到2次的状态，因此在该状态下将存在一个循环。
用您的符号，您可以与图像进行对应，这样:

您的u是图片中的x

v是图像中的y

w是图像中的z

要从 q0到 qn到达，可以使用集合中的任何字符串: { uw , uvw, uvvw, uvvvw, ... }。
在这种特殊情况下，模式 P是 y，设置的 X是 {xz xyz xyyz xyyyz ...}，而 S是 length(x)+length(y)。