8.1 TWO PUMPING LEMMAS
The pumping lemma given in Theorem 4.8 is an effective tool for showing that certain languages are not regular. Similar pumping lemmas are known for other language families. Here we will discuss two such results, one for context-free languages in general, the other for a restricted type of context-free language.
The pumping lemma for regular languages is based on the fact that all strings in a regular language must exhibit a certain repetitive pattern. If a language L contains a string that does not follow this pattern, then L cannot be regular. A similar reasoning leads to the pumping lemma for context-free languages. For regular languages, the pattern is a consequence of the finiteness of the representing dfa; with context-free ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
