Dr. Dr. Bethan Tovey-WalshDoes anyone know of a really good explanation of the pumping lemma for regular languages? I understand all the parts, I think, but I'm having trouble getting quite how they all fit together, and how they apply in practice to some types of regular language. Ideally, I'd love to see examples that are worked out step by step, on languages a bit more real-world than the traditional "a*b*" type.
Alice Brenon@linguacelta Do you mean applications of the lemma to prove that a language is *not* regular? Or are you interested in visualizing the kind of strings that would get generated by pumping a given input string ? What explanation do you know and what feels wrong with it? I usually just replace 'a' and 'b' by an opening and closing parenthesis respectively when I want a real-world example but I suppose it might not be very helpful since it doesn't change the structure at all : )
One of the major things is trying to understand why languages with a finite number of sentences are all regular. I suppose it's because, technically, you could write a grammar for that language by putting every possible sentence into it directly, without needing any non-regular features (i.e. you can express that set of sentences using only linear production rules)?
@linguacelta Yeah, when things are finite everything gets simpler (but also less informative about the general behaviour). Indeed, in that case you can simply build a path following the common content of the sentences, and fork when they differ, and you still get a finite number of nodes with a very simple structure and no loop at all and that works (and then no pumping can occur since you need a loop for that).
Riiiiiight!! Thank you! That was the thing I'd failed to note - some (finite) regular grammars can't be pumped.
Wow. Major breakthrough at last. I can't believe there was just that tiny jigsaw piece missing! Thanks so much for the help.
@linguacelta Really? I'm so glad it helped! 😌
Oh, I was going around in circles trying to work out how to pump finite grammars 😆