Infinite CFLs and Another Pumping Theorem

Explore infinite context-free languages and build up to the pumping theorem from infinite CFLs.

Intuitive reasoning behind the pumping theorem for CFLs

Now that we know how to determine if a context-free grammar generates an infinite language, let’s look a little closer at such languages. Suppose AA is a recursive variable in some CFG. Beginning with the start variable until the time AA first appears in a working derivation, symbols will have accumulated around AA. Look at the CFG below and the following derivation:

Get hands-on with 1200+ tech skills courses.