Universality for Context-Free Grammars is Undecidable
Here we show that the "universality" problem for context-free grammars is undecidable. It is similar to the E_LBA video but we instead embed strings NOT encoding "reversed" accepting computation histories into the CFG.
What is a context-free grammar? It is a set of 4 items: a set of "variables," a set of "terminals," a "start variable," and a set of rules. Each rule must involve a single variable on its "left side", and any combination of variables and terminals on its right side. See https://www.youtube.com/watch?v=h1OSmLSacNA&ab_channel=EasyTheory for more details.
▶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. ... https://www.youtube.com/watch?v=L9AKRVBSpYQ
Here we cover the regular expression (regex) to NFA conversion. The idea is to revisit the definition of regex, and to make an NFA for each of the 6 pieces of the definition. For the first three, we can make either a 1-state or a 2-state NFA. For the other three (the "inductive" cases), we revisit earlier constructions with NFAs using union, concatenation, and star to make an NFA for the "bigger" regex, using "smaller" NFAs that have already been built.
#easytheory #nfa #dfa #gate #gateconcept #theoryofcomputing #turingmachine #nfatoregex #cfg #pda #undecidable #ricestheorem
Contribute:
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Live Streaming (Sundays 2PM GMT, 2 hours):
Twitch: https://www.twitch.tv/easytheory
(Youtube also)
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
▶ADDITIONAL QUESTIONS◀
1. What does the NFA for the regex ab look like?
▶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.
...
https://www.youtube.com/watch?v=HLOAwCCYVxE
Here we look at a (rare) double conversion, which is converting from a regular grammar to an NFA (nondeterministic finite automaton) to a regular expression (regex). This comes from a 2017 exam question of mine. I walk through the steps in both of the conversions of how to perform them.
For the regular grammar to NFA conversion, make a state for each of the variables of the NFA, as well as a single final state. Then, for each rule that produces a variable, go to that variable with the produced character (or on epsilon if none produced). If a rules makes epsilon or a character, go to the new final state on that character.
For the NFA to regex conversion, I walk through this process in this video: https://www.youtube.com/watch?v=UKYvP8aS7fM&list=PLylTVsqZiRXMD7nqoHqEdCKdeGwGuO1KR&index=6&t=0s
Patreon: https://www.patreon.com/easytheory
Twitch: https://www.twitch.tv/easytheory
Mixer: https://mixer.com/easytheory
Discord: https://discord.gg/SD4U3hs
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.com/EasyTheory
Teespring: 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
▶ADDITIONAL QUESTIONS◀
1. What is the maximum length of a regex that comes from the NFA to regex process? What about for this specific NFA?
2. Will the regex that comes out of the conversion look the same if we ripped out different states? When is it the case that they are identically the same?
▶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 over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
Ho
...
https://www.youtube.com/watch?v=6SyRwpyQF6I
Here we show that Busy Beaver numbers are undecidable.
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
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
▶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.
...
https://www.youtube.com/watch?v=yCl0SGA2hg8
Here we give different proofs that EQ_DFA is decidable: (1) a different formulation of "equality" for two sets (namely regular languages), (2) minimization of DFAs, and (3) using the pumping lemma.
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
Youtube Live Streaming (Sundays) - subscribe for when these occur.
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.
...
https://www.youtube.com/watch?v=ql0rBl29_fQ
Here we convert a context-free grammar into Chomsky Normal Form, and show that it works for any CFG. The process involves 5 stages: (1) ensure the start variable is not on the RHS of any rule, (2) "eliminate" epsilon-rules, (3) "eliminate" unit rules, (4) ensure the RHS is only variables or a single terminal, and (5) reduce "long" RHSes. The order of the rules is important!
Timestamps:
0:00 - Intro
1:30 - Step 1 (ensure start var not on RHS)
3:25 - Step 2 ("eliminate" epsilon rules)
9:10 - Step 3 ("eliminate" unit rules)
13:48 - Step 4 (remove mix of terminals and vars)
17:18 - Step 5 (ensure RHSes are of length at most 2)
Patreon: https://www.patreon.com/easytheory
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. Can you prove why it is the case that each stage never changes the language of the CFG?
2. What if we have a regular grammar and convert it to CNF? (i.e., every rule is either A to epsilon, A to a single terminal, A to a variable B, or A to xB where x is a terminal, B a variable)
▶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 over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
...
https://www.youtube.com/watch?v=-SZkkMWHBvQ
Here we go over the definition of Turing Machines, as well as an example of one and how to compute with it using the Turing Machine tape. This was recorded on 3 April 2017.
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
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
▶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.
...
https://www.youtube.com/watch?v=aDK5E868lfg
Here we introduce NL-completeness, and prove that nondeterministic space classes are closed under complement (and thus NL = coNL). We also show that the PATH problem is NL-complete, and thus also give an algorithm for the complement of PATH in nondeterministic log space. The trick is to "redo" the computation over and over, and "verify" how many nodes you've seen at a certain distance from the source vertex. Once you verify the number at most the number of vertices away from the start, you must have "seen" every vertex, and thus if the target is not found, it is not reachable from the start.
What is space in complexity theory? It is the maximum amount of cells used on a Turing Machine that runs on inputs of size n. See https://www.youtube.com/watch?v=yMhQdU5j6ag&t=8s&ab_channel=EasyTheory for more details.
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Timeline:
0:00 - Intro
0:37 - NL-completeness
8:20 - Directed Path is NL-complete
14:21 - Proof Idea for the Immerman-Szelepcsényi Theorem
19:47 - Algorithm for the Immerman-Szelepcsényi Theorem
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
Youtube Live Streaming (Sundays) - subscribe for when these occur.
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
▶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.
...
https://www.youtube.com/watch?v=nBWqCv_dztY
Here we address the question of what happens if a DFA has empty alphabet? And we give another proof of a famous result regarding the empty set star.
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
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
▶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.
...
https://www.youtube.com/watch?v=K7wlqxlTTwo
Here we prove Arden's Theorem/Lemma, which says that if we have regexes A and B such that (1) epsilon is not in A, and (2) A = C U AB for some regex C, then we can uniquely write A as CB*. The idea is to "expand" out the right side until we notice a pattern, and then factor C out of the right side. Then we use the definition of star to deduce that it is indeed CB*.
#easytheory #nfa #dfa #gate #gateconcept #theoryofcomputing #turingmachine #nfatoregex #cfg #pda #undecidable #ricestheorem
Contribute:
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
Live Streaming (Sundays 2PM GMT, 2 hours):
Twitch: https://www.twitch.tv/easytheory
(Youtube also)
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
▶ADDITIONAL QUESTIONS◀
1. Prove that A = CB* is unique.
▶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.
...
https://www.youtube.com/watch?v=trBbpsaPkbc