Re: Pumping lemma. Where I go wrong?
- From: Chris Smith <cdsmith@xxxxxxx>
- Date: Sat, 7 Apr 2007 23:29:01 -0600
Ravi <ra.ravi.rav@xxxxxxxxx> wrote:
FOR ALL regular languages
THERE EXISTS a pumping length n such that
FOR ALL strings in the language
THERE EXISTS a partition into x, y, and z
such that some conditions are true.
Wikipedia says it as
Let L be a regular language. Then there exists an integer n = 1 such
that every string w in L of length at least n (n be the pumping
length) can be written as w = xyz (i.e., w can be divided into three
substrings), satisfying <some conditions>
There is no mention of
THERE EXISTS a partition into x, y, and z
It's there, just with a slightly different wording. The phrase "can be
written as w = xyz satisfying..." means that there is some division into
x, y, and z where the conditions are true. It does not mean that the
conditions are true of all possible divisions.
I wrote the lemma using wording that makes the alternating quantifiers
more explicit; Wikipedia apparently had no such motive; but both mean
the same thing.
and moreover, pumping lemma is not sufficient to prove a language is
regular, but can help if a language is not regular.
True; but I'm not sure why you're saying this right now. I don't recall
anyone talking about using the pumping lemma to prove regularity. If
someone were suggesting that, it would not be valid.
--
Chris Smith
.
- References:
- Pumping lemma. Where I go wrong?
- From: Ravi
- Re: Pumping lemma. Where I go wrong?
- From: Rick Decker
- Re: Pumping lemma. Where I go wrong?
- From: Ravi
- Re: Pumping lemma. Where I go wrong?
- From: Chris Smith
- Re: Pumping lemma. Where I go wrong?
- From: Ravi
- Pumping lemma. Where I go wrong?
- Prev by Date: Re: Pumping lemma. Where I go wrong?
- Next by Date: Re: "Size Balanced Tree" - more efficient than any known algorithm?
- Previous by thread: Re: Pumping lemma. Where I go wrong?
- Next by thread: Re: "Size Balanced Tree" - more efficient than any known algorithm?
- Index(es):
Relevant Pages
|
