LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Confusion in Pumping Lemma (PL) as presented in book by: Arthur Fleck. (https://www.linuxquestions.org/questions/programming-9/confusion-in-pumping-lemma-pl-as-presented-in-book-by-arthur-fleck-4175730557/)

ajiten 11-04-2023 04:37 AM

Confusion in Pumping Lemma (PL) as presented in book by: Arthur Fleck.
 
5 Attachment(s)
Regarding the concept of pumping length, in Pumping Lemma (PL), have some confusion in the presentation in the book titled: Formal Models Of Computation, by Arthur Fleck.
It states on page #91 (attached herewith, & accessed via subscription to Perlego) that the pumping length (N) is given, for a regular language L ⊆ Σ*, as:

for each string z ∈ L, with len(z) ∈ N, there exist (sub-strings of the string z) u, v & w ∈ Σ*, so that:
(i) string z is a concatenation of u, v & w; i.e. z = uvw,
(ii) len(uv) ≤ N and len(uv) ≥ 1,
(iii) uv^kw L; for all non-negative integer values for k.

.........................................

Doubt #1: The length of string (z) is stated to be in the range from 0...N; rather than having length at-least equal to the pumping length (N).
Though, the point (ii) states that len(uv) ≤ N, still it does no help.

In the site here, it is clearly stated that the length of the string (s) is at least equal to the pumping length (p); i.e. states |s| ≤ p.

----------
The doubt intensifies when you do not get any clue in the book, in further down pages; as shown attached herewith (till page #95; and few more pages attached in the next message).

ajiten 11-04-2023 04:58 AM

Further pages in the book, after page #95, till the end of the presentation of the topic of PL.
 
3 Attachment(s)
The book presents the topic of PL for regular languages, till page #97.
But, the book still has mention of PL, in the context of operations overcoming the limitations of PL, on page #98.
So, added till page #98.

I know that page #98, is unnecessary; but added as consider it as the best book on the topic (& in general, on formal languages, from the UG viewpoint); so might need help later on topic started on page #98.

astrogeek 11-05-2023 02:30 PM

Quote:

Originally Posted by ajiten (Post 6462727)
...
It states on page #91 (attached herewith, & accessed via subscription to Perlego) that the pumping length (N) is given, for a regular language L ⊆ Σ*, as:

for each string z ∈ L, with len(z) ∈ N, there exist (sub-strings of the string z) u, v & w ∈ Σ*, so that:
(i) string z is a concatenation of u, v & w; i.e. z = uvw,
(ii) len(uv) ≤ N and len(uv) ≥ 1,
(iii) uv^kw L; for all non-negative integer values for k.

.........................................

Doubt #1: The length of string (z) is stated to be in the range from 0...N;...

Regarding the first red hilighted part - what would that even mean? You have substituted the symbol for element of, '∈', for what is clearly a typo in the image of page 91 which looks like the epsilon character, 'ε', and also makes no sense.

The typo looks like an OCR error, so I would be very cautious about reading any of those pages, especially of non-alphabetic characters which have a higher rate of OCR errors in my experience.

Item (ii) contains a transcription error.

Regarding the Doubt #1 hilight, I do not see that statement on that page, but have not looked at others. But in view of the probability of other OCR errors I think it is moot.

I would suggest that you find a better quality version of this text, or another source entirely, and start over.

Quote:

Originally Posted by ajiten (Post 6462727)
In the site here, it is clearly stated that the length of the string (s) is at least equal to the pumping length (p); i.e. states |s| ≤ p.

That is self contradictory, so this question also makes no sense.

ajiten 11-06-2023 05:36 AM

Quote:

Originally Posted by astrogeek (Post 6463045)
Regarding the first red hilighted part - what would that even mean? You have substituted the symbol for element of, '∈', for what is clearly a typo in the image of page 91 which looks like the epsilon character, 'ε', and also makes no sense.

The typo looks like an OCR error, so I would be very cautious about reading any of those pages, especially of non-alphabetic characters which have a higher rate of OCR errors in my experience.

Regarding the second hilight, I do not see that statement on that page, but have not looked at others. But in view of the probability of other OCR errors I think it is moot.

I would suggest that you find a better quality version of this text, or another source entirely, and start over.



That is self contradictory, so this question also makes no sense.

I hope your last line means that should have used '≥', instead of '≤', i.e.:
'... it is clearly stated that the length of the string (s) is at least equal to the pumping length (p); i.e. states |s| ≥ p.'

If so, kindly ignore it as a typo.

RubyBennett 11-17-2023 03:57 AM

The Pumping Lemma, as presented in Arthur Fleck's book, implies that for a regular language \(L\), the length of \(z\) should be at least equal to the pumping length \(N\). Clarification may be sought in subsequent pages or additional resources. I found this https://stateofwriting.com/ website for writing service called State of Writing has completely transformed my academic experience. When I was overwhelmed with a stack of assignments, I sought out their custom writing and editing services. The effect was remarkable - my papers now exhibit a level of professionalism and precision that I had not previously achieved. The team at the State of Writing not only met deadlines but went beyond my expectations, clearly demonstrating their dedication to student success.


All times are GMT -5. The time now is 12:17 PM.