Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
It's actually maddening that I've spent hours with my professors trying to wrap my head around concepts like this and you destroy almost all my doubts in just 18 minutes haha, thank you so much for all of your vids!
Exercise from video: Proving PAL isn't regular. We will prove this with the pumping lemma. First, assume PAL is regular, so it has a pumping constant p. Take the string w=(0^p)1(0^p). This is in PAL because it is a palindrome, and it has a length greater than p. Then, set w=xyz, where |y|>0 and |xy|0) z=(0^p-a-b)1(0^p) Then, by the pumping lemma, we know all x(y^i)z are in PAL. Take i=2: x(y^2)z = (0^a)(0^b)(0^b)(0^p-a-b)1(0^p) = (0^p+b)1(0^p) This can only be in PAL if it's a palindrome, which is only possible if the zero's on the left and right size of the 1 are equal. So we have: p+b=p --> b=0 Which is a contradiction because we know the length of y is greater than 0. Therefore, PAL can not be regular.
Thanks for the video you are really saving lives here. My prof just gave us 2 powerpoint slides not even videos or lectures. I'd like to request videos solving problems from the book. The biggest challenge I'm finding is that lectures like yours can be very helpful but the problems are just way harder. Anything helps. Keep it up!
I have some already made. Will make more. Here's the playlist of the ones I've already done: ua-cam.com/video/CvQDtQNqfAw/v-deo.html&ab_channel=EasyTheory
Great example my prof went over this one in class but just wasnt getting it. Glad u used sipsor as well !! i saw ur recent video about whats the point as well and loved that view as i was one who thought the more negative way of things. hope ur doing well !
CFG is basically the axiom of specification in set theory... well, not equivalently speaking, but the same concept applies. Every A and every conditional; exists B, which holds all membership A and A's conditions.
After watching the video I came up with these doubts: Does the language of even-length palindromes form a context-free grammar? Does the language of words that have more a's than b's form a context-free grammar? Can every grammar be simplified to a regular grammar?
1. In case of language of even length palindrome strings over any 2 terminals, yes, its grammar is indeed a CFG. You can create a PDA for this which in turn proves that its a CFG. 2. It is also a CFL as you can create its PDA 3. As per Chomsky Hierarchy we know that a regular grammar is also a recursively enumurable grammar but thats not vice versa. So, you cannot simplify any grammar into a regular grammar. The languages differ.
Thank you so much, I know you might not think anyone is watching but I am thankful I clicked and it wasn't another Indian because they've been haunting my dreams.
Every regular language is context-free, so a CFG can always be made for a regular language. Note that every regular language has a regular grammar, which already is a CFG.
@@MsCrycry not strictly speaking. The only allowed rule types are of the form A -> x, where A is a single variable, and x is empty string, a single terminal, a single variable, OR a single terminal then a single variable. So those rules are not in the allowed rule types. However, they describe a regular language, so there exists a regular grammar for it (just that it's not involving the rules you gave).
This is the worst class. You dont realize how lucky you are that you have hundreds of years of pedagogy behind math until you take theoretical computer science classes and see how makeshift the pedagogy is.
Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Hey man, just wanted to say I really appreciate you taking the time to make a video like this. Your work does not go unnoticed!
Much thanks for watching
It's actually maddening that I've spent hours with my professors trying to wrap my head around concepts like this and you destroy almost all my doubts in just 18 minutes haha, thank you so much for all of your vids!
This video came just in time, I just finished my exam a few minutes ago. I don't think there's any way I would have passed without your videos!
You're very welcome, and good luck!
Exercise from video: Proving PAL isn't regular.
We will prove this with the pumping lemma. First, assume PAL is regular, so it has a pumping constant p.
Take the string w=(0^p)1(0^p). This is in PAL because it is a palindrome, and it has a length greater than p.
Then, set w=xyz, where |y|>0 and |xy|0)
z=(0^p-a-b)1(0^p)
Then, by the pumping lemma, we know all x(y^i)z are in PAL. Take i=2:
x(y^2)z = (0^a)(0^b)(0^b)(0^p-a-b)1(0^p) = (0^p+b)1(0^p)
This can only be in PAL if it's a palindrome, which is only possible if the zero's on the left and right size of the 1 are equal. So we have:
p+b=p --> b=0
Which is a contradiction because we know the length of y is greater than 0.
Therefore, PAL can not be regular.
Great job!
Perfect.
speed running your videos for finals tomorrow, thanks for the knowledge
Thanks for the video you are really saving lives here.
My prof just gave us 2 powerpoint slides not even videos or lectures.
I'd like to request videos solving problems from the book. The biggest challenge I'm finding is that lectures like yours can be very helpful but the problems are just way harder. Anything helps. Keep it up!
I have some already made. Will make more. Here's the playlist of the ones I've already done: ua-cam.com/video/CvQDtQNqfAw/v-deo.html&ab_channel=EasyTheory
Thank you so much for making detailed and informative videos like this, thanks to you I feel more confident for my exam tomorrow :)
Good luck!
Great example my prof went over this one in class but just wasnt getting it. Glad u used sipsor as well !! i saw ur recent video about whats the point as well and loved that view as i was one who thought the more negative way of things. hope ur doing well !
The best lesson's creator for this subject
Please decrease the amount of adds this is so annoying!!!!!
that's great, you're making Autumata much more interesting.
Thank you for taking the time to make this man! This is much better explained than my teacher haha
You're welcome! Make sure to send this to everyone you know ;)
The way you teach is so good!!!!
Thanks for the video man, it's really helpful
Bro you just saved my exam thanks!
CFG is basically the axiom of specification in set theory... well, not equivalently speaking, but the same concept applies. Every A and every conditional; exists B, which holds all membership A and A's conditions.
2024- Still best series so far!
Thank you for the video! It really helps out since my prof Obrenic sucks at teaching. :)
Thanks!
This was so helpful! Thank you!!
You're very welcome!
thank you for not having a thick indian accent
looooool
you're an actual hero.
Amazing Explanation !
Also can you tell me the name of the theme playing in your channel intro , it sounded really good !
Amazing explanation. I bet you a five year old can easily understand CFG by watching this video :-) Thank you!
After watching the video I came up with these doubts:
Does the language of even-length palindromes form a context-free grammar?
Does the language of words that have more a's than b's form a context-free grammar?
Can every grammar be simplified to a regular grammar?
1. In case of language of even length palindrome strings over any 2 terminals, yes, its grammar is indeed a CFG. You can create a PDA for this which in turn proves that its a CFG.
2. It is also a CFL as you can create its PDA
3. As per Chomsky Hierarchy we know that a regular grammar is also a recursively enumurable grammar but thats not vice versa. So, you cannot simplify any grammar into a regular grammar. The languages differ.
Would this also work as a CFG for PAL?:
S = 0A | 1B | 0 | 1 | E
A = 0 | S0
B = 1 | S1
thanks for helping me understand this stuff, instant subscribe!
Where were you when I took theory of computation :(
In your context-free dreams
Thanks for the video!
You are amazing thank you so much!!!!!!! Very good explanation :)))
You're very welcome!
Can you tell me what’s the name this application you use?
Great video! Do you maybe have video on generation trees and Lukasiewicz notation? It's in the CFG chapter of Cohen's book
Thank you so much, I know you might not think anyone is watching but I am thankful I clicked and it wasn't another Indian because they've been haunting my dreams.
Lmao thanks for your viewership! I do read all comments :)
@@EasyTheory shared your videos and playlist with all my class mates. Thank you so much for your time.
@@Marcalitus Much appreciated!
Agreed. Much love to my fellow Americans.
Would this work for palindromes?
S -> 0 | 1 | E | 0B0 | 1B1, B ->0B | 1B | E
01100 in language but not a palindrome
holy crap THANK YOU
thank you so much for this
Nice explanation
by any chance, a CFG cannot generate a regular language?? and what is the best way to prove if a CFG can or cannot generate regular language?
Every regular language is context-free, so a CFG can always be made for a regular language. Note that every regular language has a regular grammar, which already is a CFG.
@@EasyTheory Thank you for your help. Btw is S -> Aaa or S -> aa are also regular grammar?
@@MsCrycry not strictly speaking. The only allowed rule types are of the form A -> x, where A is a single variable, and x is empty string, a single terminal, a single variable, OR a single terminal then a single variable. So those rules are not in the allowed rule types.
However, they describe a regular language, so there exists a regular grammar for it (just that it's not involving the rules you gave).
Very good video and damn, you're attractive, and so is your voice
thaaanks a lot
Professor, at 4:20 you inserted a comma into the string!
Thank you, sir :)
You're welcome!
Thanks!
Tnx man😅
goated
5 minutes in and i have no idea what you're saying.
ur so cool....
handsome and smart
I have never hated a class or subject more than this
intro music is out of time
This is the worst class. You dont realize how lucky you are that you have hundreds of years of pedagogy behind math until you take theoretical computer science classes and see how makeshift the pedagogy is.