Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
