LinuxQuestions.org
Visit Jeremy's Blog.
Home Forums Tutorials Articles Register
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 11-04-2023, 04:37 AM   #1
ajiten
Member
 
Registered: Jun 2023
Posts: 377

Rep: Reputation: 4
Confusion in Pumping Lemma (PL) as presented in book by: Arthur Fleck.


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).
Attached Thumbnails
Click image for larger version

Name:	91.jpg
Views:	18
Size:	142.4 KB
ID:	41985   Click image for larger version

Name:	92.jpg
Views:	9
Size:	130.0 KB
ID:	41986   Click image for larger version

Name:	93.jpg
Views:	8
Size:	147.3 KB
ID:	41987   Click image for larger version

Name:	94.jpg
Views:	9
Size:	136.1 KB
ID:	41988   Click image for larger version

Name:	95.jpg
Views:	7
Size:	156.9 KB
ID:	41989  


Last edited by ajiten; 11-04-2023 at 04:52 AM.
 
Old 11-04-2023, 04:58 AM   #2
ajiten
Member
 
Registered: Jun 2023
Posts: 377

Original Poster
Rep: Reputation: 4
Further pages in the book, after page #95, till the end of the presentation of the topic of PL.

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.
Attached Thumbnails
Click image for larger version

Name:	96.jpg
Views:	8
Size:	146.5 KB
ID:	41990   Click image for larger version

Name:	97.jpg
Views:	7
Size:	147.4 KB
ID:	41991   Click image for larger version

Name:	98.jpg
Views:	4
Size:	132.3 KB
ID:	41992  

Last edited by ajiten; 11-04-2023 at 05:25 AM.
 
Old 11-05-2023, 02:30 PM   #3
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,269
Blog Entries: 24

Rep: Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206Reputation: 4206
Quote:
Originally Posted by ajiten View Post
...
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 View Post
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.

Last edited by astrogeek; 11-06-2023 at 01:36 PM. Reason: better wording, tpoys
 
Old 11-06-2023, 05:36 AM   #4
ajiten
Member
 
Registered: Jun 2023
Posts: 377

Original Poster
Rep: Reputation: 4
Quote:
Originally Posted by astrogeek View Post
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.
 
Old 11-17-2023, 03:57 AM   #5
RubyBennett
LQ Newbie
 
Registered: Nov 2023
Posts: 1

Rep: Reputation: 0
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.

Last edited by RubyBennett; 11-22-2023 at 01:36 AM.
 
  


Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
LXer: Open sourcerers drop sick Fedora Remix to get Windows Subsystem for Linux pumping LXer Syndicated Linux News 0 01-24-2019 08:12 PM
LXer: Sorry Google, it's boring old workloads that are pumping up AWS and Azure, not sexy AI LXer Syndicated Linux News 0 05-18-2017 07:50 PM
Sendmail not pumping efficiently?? your_shadow03 Linux - Newbie 2 02-25-2009 09:59 AM
LXer: Google is pumping $5.6 million into open source this summer LXer Syndicated Linux News 0 04-24-2008 01:30 AM
'Lemma: ACPI Slowing Me Down.. but necessary! MiMiCx10 Linux - Newbie 4 11-15-2004 08:45 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 04:58 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration