Here we prove a "pumping lemma" for linear languages and give an example of a language that is context-free but not linear. A linear grammar is one where every rule has at most one variable on its right side, and a linear language is one that has a linear grammar for it. We have then shown that regular languages are a strict subset of linear languages, which are a strict subset of context-free languages.
Timeline:
0:00 - Intro
0:35 - Example of Linear Language
1:55 - Proof of PL for Linear Languages
14:05 - Pumping Lemma Statement
16:55 - Example for {a^i b^i c^j d^j : i, j at least 0} not linear
Easy Theory Website: https://www.easytheory.org
Discord: https://discord.gg/SD4U3hs
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
[email protected]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
