0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 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
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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

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