Complete Proof of an Inherently Ambiguous Context-Free Language - Easy Theory
Here we break the Easy Theory record on the longest "content" video! We prove that a particular context-free language is inherently ambiguous (meaning that every grammar for it is ambiguous, which is deriving some string in at least two ways). The proof is straightforward although technical. We subdivide the proof into 10 sections to assist with moving through the proof. Note that this is a first on Youtube (and other than the paper from which it originates, the only complete one explained on the internet). The original paper is "A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language" by Maurer, link here: https://dl.acm.org/doi/abs/10.1145/321510.321517.
(Note: there is a "simpler" proof we will eventually show on the channel using a tool called "Ogden's Lemma", but this is a direct and self-contained proof.)
Timestamps:
0:00 - Intro
0:28 - Part 1: What is the language?
4:23 - Part 2: Proof L is context-free
10:13 - Part 3: What is a "reduced" grammar?
17:00 - Part 4: What is an "almost looping" grammar?
20:45 - Part 5: Proof of unambiguous almost looping CFG
32:16 - Part 6: The "Big" Lemma Statement
41:07 - Part 7: Every variable is at least one of the three types
56:40 - Part 8: Every variable is exactly one of the three types
1:02:55 - Part 9: Proving the last two cases
1:09:18 - Part 10: Proving the final theorem
For more information about CFGs and CNF, check out the following playlist:
Context-Free Grammars: https://www.youtube.com/watch?v=h1OSmLSacNA&list=PLylTVsqZiRXOlDr8PemE5hUTVMGZrLD7G
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory #gate #theory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶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.
Видео Complete Proof of an Inherently Ambiguous Context-Free Language - Easy Theory канала Easy Theory
(Note: there is a "simpler" proof we will eventually show on the channel using a tool called "Ogden's Lemma", but this is a direct and self-contained proof.)
Timestamps:
0:00 - Intro
0:28 - Part 1: What is the language?
4:23 - Part 2: Proof L is context-free
10:13 - Part 3: What is a "reduced" grammar?
17:00 - Part 4: What is an "almost looping" grammar?
20:45 - Part 5: Proof of unambiguous almost looping CFG
32:16 - Part 6: The "Big" Lemma Statement
41:07 - Part 7: Every variable is at least one of the three types
56:40 - Part 8: Every variable is exactly one of the three types
1:02:55 - Part 9: Proving the last two cases
1:09:18 - Part 10: Proving the final theorem
For more information about CFGs and CNF, check out the following playlist:
Context-Free Grammars: https://www.youtube.com/watch?v=h1OSmLSacNA&list=PLylTVsqZiRXOlDr8PemE5hUTVMGZrLD7G
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory #gate #theory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶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.
Видео Complete Proof of an Inherently Ambiguous Context-Free Language - Easy Theory канала Easy Theory
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![GATE 2020 Question 42 (p Factorial Trick, Hard Pumping Lemma!) - Easy Theory](https://i.ytimg.com/vi/qVnXMXt6Ww0/default.jpg)
![Music as a Language: Victor Wooten at TEDxGabriolaIsland](https://i.ytimg.com/vi/2zvjW9arAZ0/default.jpg)
![How to learn any language in six months | Chris Lonsdale | TEDxLingnanUniversity](https://i.ytimg.com/vi/d0yGdNEWdn0/default.jpg)
![The language of lying — Noah Zandan](https://i.ytimg.com/vi/H0-WkpmTPrM/default.jpg)
![cs461 CFG 2 CNF Context Free Grammar to Chomsky Normal Form](https://i.ytimg.com/vi/jLUmXoN1Rck/default.jpg)
![What is a graph? Endless Definitions! - Easy Theory](https://i.ytimg.com/vi/iwcqjM-shQI/default.jpg)
![Context-Free Grammar Definitions (Yields, Inherently Ambiguous, Leftmost Derivation) - Easy Theory](https://i.ytimg.com/vi/o64uz2K2S4E/default.jpg)
![What even IS a PDA (Pushdown Automaton)? Motivation + Description - Easy Theory](https://i.ytimg.com/vi/Br44Zxv84-Q/default.jpg)
![A PDA example for {0^n 1^n : n at least 0} - Easy Theory](https://i.ytimg.com/vi/SSJ0i-I2VXU/default.jpg)
![The Concept of Language (Noam Chomsky)](https://i.ytimg.com/vi/hdUbIlwHRkY/default.jpg)
![Regular Languages Closed Under Inverse (Homo)Morphism - Easy Theory](https://i.ytimg.com/vi/utlPZgorDLg/default.jpg)
![Context-Free Grammar to Pushdown Automaton (CFG to PDA Conversion) - Easy Theory](https://i.ytimg.com/vi/ZImtQBMSW_Y/default.jpg)
![Mod-01 Lec-20 Introduction to context free languages (cfls)](https://i.ytimg.com/vi/6b40kKe2SFg/default.jpg)
![Definition: Context-Free Grammars](https://i.ytimg.com/vi/I6K-QuE87NM/default.jpg)
![Removing Trailing Zeroes is Regular! (Quotient Language Example) - Easy Theory](https://i.ytimg.com/vi/xBtj0-miWNM/default.jpg)
![The Most Beautiful Equation in Math](https://i.ytimg.com/vi/IUTGFQpKaPU/default.jpg)
![The "Master" Theorem/Method, Derivation - Easy Theory](https://i.ytimg.com/vi/ZGmUTe1uiE0/default.jpg)
![An Experiment in Gratitude | The Science of Happiness](https://i.ytimg.com/vi/oHv6vTKD6lg/default.jpg)
![WHY do we have the three Pumping Lemma Conditions? - Easy Theory](https://i.ytimg.com/vi/e4dUJ8NLjeA/default.jpg)
![Everything and Nothing: What is Nothing? (Jim Al-Khalili) | Science Documentary | Science](https://i.ytimg.com/vi/rKPv8zApee0/default.jpg)