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?

  • 2
    $\begingroup$ what is a "minimum permanent"? $\endgroup$ – Hendrik Jan Jan 6 '17 at 16:59
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 7 '17 at 23:11

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:

enter image description here

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.

  • $\begingroup$ 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 $\endgroup$ – Joe Jan 7 '17 at 18:40
  • $\begingroup$ @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. $\endgroup$ – Rick Decker Jan 11 '17 at 17:37

protected by Community Jan 11 '17 at 19:06

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.