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). |
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. |
Quote:
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:
|
Quote:
'... 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. |
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. |