抽吸引理(常规语言)
mrj*_*min 5 automata pumping-lemma regular-language formal-languages
我需要一些泵浦引理问题的帮助.
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,如抽水引理中所述.如果我"抽"(bb)^ 2然后我得到
y = abbbbc^n which violates the rule #b(L) < #c(L).
这是正确的吗 ？我是在"正确的道路上"吗？
谢谢
泵引理的主要思想是告诉你,当你有一个L包含无数个术语的常规语言时,语言中的模式会永远重复.
与该语言相关的正则表达式将包含KLEENE-STAR(模式).
与该正则表达式(和语言)相关联的自动机将包含一个循环.
证明是使用鸽子原则完成的.
这个 
很有启发性.
请注意,在这种情况下,所有术语必须从q0开始并以qn结尾.因此,定义语言的自动机是有限的(最多N个状态),因此存在有限数量的状态,但是单词(即术语)可以具有> N个字母.鸽子原则告诉我们必须有一个达到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).