这个证据与抽水引理(没有常规语言)好吗?

问题描述 投票:0回答:1

我需要证明给定的语言不规律,这可行吗?

语言是M={a^m a^l c b^(m+l)|m,l in N},字母= {a,b,c}

证明:

Be n in N arbitrary but firm. We choose the word w=a^(2n)cb^(2n) with w in M and |w|>=n.
Be w=xyz a arbitrary decomposition with y!=lambda and |xy|<=n.
Then we have x=a^(2i), y=a^(2j) and z= a^(2n-2i-2j)cb^(2n) for j!=0 and 2(i+j)<=2n.
Now we choose k=0. The we have xy^0z=a^(2n-2i)cb^(2n).
=> xy^0z is not in M because 2n-2i!=2n for j!=0.
=> M is no regular language.

是啊还是不?如果你能告诉我我的错误,我将非常感激

regular-language proof pumping-lemma
1个回答
0
投票

你的想法是对的。只是一些细节:

“固定”而非“坚定”(德语翻译?)

你需要区分你选择的n和常数与泵浦引理(你没有选择)。

所以:

Let K be the constant for M from the pumping lemma and let n be a natural number such that n>K.
We choose the word w=a^(2n)cb^(2n) with w in M  and |w|>=K.
Be w=xyz a arbitrary decomposition with y!=lambda and |xy|<=n.
Then we have x=a^(2i), y=a^(2j) and z= a^(2n-2i-2j)cb^(2n) for j!=0 and 2(i+j)<=2n.
Now we choose k=0. The resulting word is xy^0z=a^(2n-2i)cb^(2n).
xy^0z is not in M because 2n-2i!=2n for j!=0.
=> M is no regular language.
© www.soinside.com 2019 - 2024. All rights reserved.