# How to Find the minimum permanent which is pumping lemma for language context-free?

Suppose we have context-free language and we know the Context-Free-Grammar, how do i found the minimum permanent which is pumping lemma for language ?

for example let sat i have this Grammar: \begin{align} S&\rightarrow AA\mid B\\ A&\rightarrow 0A\mid A0∣1\\ B&\rightarrow 00B0\mid 1\\ \end{align} whats is the best way to find this Minimum permanent?

• what is a "minimum permanent"? – Hendrik Jan Jan 6 '17 at 16:59
• It looks like you've inadvertently created multiple accounts. I encourage you to merge them: cs.stackexchange.com/help/merging-accounts. Retaining access to the account you posted the question with is helpful: it enables you to post comments under answers to your question. – D.W. Jan 7 '17 at 23:11

## 1 Answer

I presume by "permanent" you mean the integer of the Pumping Lemma, that is the integer $$p>0$$ such that for any string $$s$$ in the language with length $$p$$ or greater we can express $$s=uvxyz$$ with . . . [blah blah blah, I'm not going to write the statement here].

If you've read the proof of the PL, you know that it relies on guaranteeing that in a parse tree for a string of sufficient length, there will always be some path from the root to a leaf which contains a repeated variable. When that happens, we can replace the subtree rooted at the "lower" repeated variable with a copy of the subtree rooted at the "upper" repeated variable and have a parse tree for a new string also in the language: i.e., you've pumped the string.

For the grammar you've given, it is particularly easy to find the shortest strings in the language with a repeated variable in a path from the root to a leaf. Here are the trees for the shortest such strings: There are two other of the right-hand form, but because of the way your grammar is formed, any string of length greater than or equal to 3 generated by the grammar must be formed by extending one of these two. In other words, the integer of the pumping lemma can be 3 or greater. It can't be 1 or 2, since while the strings $$1$$ and $$11$$ are in the language, there are no repeated variables in their parse trees (meaning they can't be pumped). Finally, then, the integer you want is 3.

• if you pick the integer to be 3 ,than you have a Problem with choose VXY to the string 0010 , how can you explain it? @Rick Decker #Rick Decker – Joe Jan 7 '17 at 18:40
• @Joe. If we decompose 0010 with $u=\epsilon, v=00, x=1, y=0, z=\epsilon$ then pumping down yields the string 1, which is in the language. I don't see the problem here. – Rick Decker Jan 11 '17 at 17:37