Re: pumping lemma question
- From: Chris Smith <cdsmith@xxxxxxx>
- Date: Tue, 26 Dec 2006 20:47:22 -0700
3ashmawy <3ashmawy@xxxxxxxxx> wrote:
I always get confused by "pumping up" and "pumping down" notations.
Could someone clarify it for me. and weather it have a different
meaning for Context free languages.
The pumping lemma for regular language states that under the given
conditions, there's a partition x = uvw, such that u(v^i)w is in the
language for all i greater than OR EQUAL TO zero. Since uvw was a
partition of a string in the language, you have the i = 1 case
trivially. As informal terms, "pumping up" just means that you are
considering a case where i > 1, and "pumping down" means that you are
considering the case i = 0. Note that neither "pumping up" nor "pumping
down" are mentioned in any formal statement of the pumping lemma. I'm
not even convinced that it's pedagogically sound to make the
distinction. But many people do.
For example, suppose my string is abbaaabbaba, and I partition it as
(abba)(aab)(baba), where the parens are only used for grouping and are
not part of the alphabet. Then "pumping down" means that I look at the
string (abba)(baba) [without the parens: abbababa] to ensure that it is
in the language. On the other hand, pumping up would mean looking at
something like (abba)(aab)(aab)(baba).
The pumping lemma for context-free languages has pretty much exactly the
same meaning; the partition is x = pqrst, and p(q^i)r(s^i)t is
guaranteed to be in the language, again for all i greater than or equal
to zero. The terms "pumping up" and "pumping down" mean the same thing:
that you are considering the case i > 1, or i = 0, respectively.
Does that help?
--
Chris Smith
.
- References:
- pumping lemma question
- From: 3ashmawy
- pumping lemma question
- Prev by Date: Re: Division by zero
- Next by Date: Re: Which Algorithm is Faster?
- Previous by thread: pumping lemma question
- Next by thread: Division by zero
- Index(es):
Relevant Pages
|
