用上下文无关语言泵送引理 [英] Pumping Lemma with Context Free Languages

问题描述

我使用的语言是{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 我首先假设为我选择了一些m，使得一个字符串

   z = a^m b^(m-1) c^(m-2)

然后将字符串拆分为(z =) uvwxy，以使vx不为空，而#(vwx)<=m 然后，当我选择"i"时，我会感到困惑.假设我选择i=1，那么我有: uv^1wx^1y，我不确定该从何而来，因为在我看来 就像我可以选择该语言中的vwx.

有什么建议吗?

解决方案

我首先选择一个更好的z = a ^(m + 2)b ^(m + 1)c ^(m)，其中m是抽水长度.该字符串显然是该语言的语言，并且其长度大于或等于m.因此，假设该语言是CFL，则适用抽水式引理.现在，既然您知道| vwx | < = m和| vx | > 0，您还知道vwx必须由(1)仅一个a，(2)一些a和一些b，(3)仅b'，(4)一些b和某些c或(5)仅c组成.

分别处理每种情况.我将为您处理前两种情况.

情况1:这意味着vx在s> 0时是a ^(s)，因为引理告诉我们| vx |. >0.现在假设i =0.则引理告诉我们z'= uv ^(0)wx ^(0)y仍应属于该语言.但是，z'的形式为a ^(m + 2-s)b ^(m + 1)c ^(m)，并且由于s> 0，因此违反了a的数量必须严格大于a的条件. b的个数.因此z'不在语言中，这种情况下无法抽出.

情况2:这意味着对于某些s，t，vx是a ^(s)b ^(t)，使得s + t>0.再次假设，我取i = 0.形成a ^(m + 2-s)b ^(m + 1-t)c ^(m).如果t为正，则违反了b的数量严格大于c的数量的条件.如果t为零，则s必须为正，在这种情况下，我们会退化为情况1.因此z'不在语言中，并且这种情况无法泵浦.

要处理其他情况，请记住，您可以为每个选择一个不同的抽运指数.

(根据有关该问题的以往讨论，我决定展示其他三种情况.)

情况3:这意味着对于某些s> 0，vx是b ^(s).取i =0.则z'的形式为a ^(m + 2)b ^(m + 1-s) c ^(m).由于s为正，因此违反了b的数量严格大于c的数量的条件.因此，z'不是该语言的语言，因此这种情况无法执行. (您也可以将i等于1以外的任何值，以表明这种情况无法发挥作用.)

情况4:这意味着对于某些s，t，vx是b ^(s)c ^(t)，使得s + t>0.取i =2.则z'的形式为a ^(m +2)b ^(m + 1 + s)c ^(m + t).如果s不为零，则违反a的数量严格大于b的数量的条件.如果s为零，则t必须为非零，在这种情况下，违反了b的数量严格大于c的数量的条件.因此，z'不是该语言的语言，这种情况下也无法执行.

情况5:这意味着对于某些s> 0，vx是c ^(s).取i =2.则z'的形式为a ^(m + 2)b ^(m + 1)c ^ (m + s).由于s为正，因此违反了b的数量严格大于c的数量的条件.因此，z'不是该语言的语言，这种情况下无法执行.

由于所有五个案例均无法抽出，抽引式告诉我们，该语言不是上下文无关的.

I have the language {a^i b^j c^k | i,j,k>=0 & i>j & j>k} I began by assuming some m is picked for me, such that a string

   z = a^m b^(m-1) c^(m-2)

Then the string is split up into (z =) uvwxy so that vx are not empty and #(vwx)<=m Then when I get to pick an "i" I get confused. Say I pick i=1 then I have: uv^1wx^1y and I'm not entirely sure where to go from that because to me it looks like I could pick a vwx that IS in the language.

Any suggestions?

解决方案

I'd begin by picking a slightly better z = a^(m+2)b^(m+1)c^(m), where m is the pumping length. This string is clearly in the language and its length is greater than or equal to m. So, assuming the language is a CFL, the pumping lemma applies to it. Now, since you know that |vwx| <= m and that |vx| > 0, you also know that vwx must consist of (1) only a's, (2) some a's and some b's, (3) only b's, (4) some b's and some c's, or (5) only c's.

Deal with each case individually. I'll do the first two cases for you.

Case 1: This means that vx is a^(s) for some s > 0, since the lemma tells us |vx| > 0. Now suppose you take i = 0. Then the lemma tells us that z' = uv^(0)wx^(0)y should still belong to the language. However, z' is of the form a^(m+2-s)b^(m+1)c^(m) and, since s > 0, violates the condition that the number of a's must be strictly greater than the number of b's. Thus z' is not in the language, and this case fails to pump.

Case 2: This means that vx is a^(s)b^(t) for some s,t such that s+t > 0. Suppose, again, you take i = 0. Then z' is of the form a^(m+2-s)b^(m+1-t)c^(m). If t is positive, then the condition that the number of b's be strictly greater than the number of c's is violated. If t is zero, s must be positive, in which case we degenerate to case 1. Thus z' is not in the language, and this case fails to pump.

For dealing with the other cases, remember that you can pick a different pumping exponent i for each one.

Edit: (From past discussion on this question, I had decided to show the other three cases.)

Case 3: This means that vx is b^(s) for some s > 0. Take i = 0. Then z' is of the form a^(m+2)b^(m+1-s)c^(m). Since s is positive, this violates the condition that the number of b's be strictly greater than the number of c's. So z' is not in the language and this case fails to pump. (You could also take i equal to anything but 1 to show that this case fails to pump.)

Case 4: This means that vx is b^(s)c^(t) for some s,t such that s+t > 0. Take i = 2. Then z' is of the form a^(m+2)b^(m+1+s)c^(m+t). If s is nonzero, then the condition that the number of a's be strictly greater than the number of b's is violated. If s is zero, then t must be nonzero, in which case the condition that the number of b's be strictly greater than the number of c's is violated. So z' is not in the language and this case also fails to pump.

Case 5: This means that vx is c^(s) for some s > 0. Take i = 2. Then z' is of the form a^(m+2)b^(m+1)c^(m+s). Since s is positive, the condition that the number of b's be strictly greater than the number of c's is violated. So z' is not in the language and this case fails to pump.

Since all five cases fail to pump, the Pumping Lemma tells us that this language is not context-free.

这篇关于用上下文无关语言泵送引理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！