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 is a recursive variable in some CFG. Beginning with the start variable until the time first appears in a working derivation, symbols will have accumulated around . Look at the CFG below and the following derivation:
Get hands-on with 1400+ tech skills courses.