Thanks to my supporters Yuri, vinetor, Ali (RUclips) 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: ruclips.net/video/CvQDtQNqfAw/видео.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.
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.
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.
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 (RUclips) 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!
speed running your videos for finals tomorrow, thanks for the knowledge
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.
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: ruclips.net/video/CvQDtQNqfAw/видео.html&ab_channel=EasyTheory
The best lesson's creator for this subject
Please decrease the amount of adds this is so annoying!!!!!
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!
that's great, you're making Autumata much more interesting.
The way you teach is so good!!!!
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 !
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 ;)
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.
Bro you just saved my exam thanks!
Thanks for the video man, it's really helpful
This was so helpful! Thank you!!
You're very welcome!
Thank you for the video! It really helps out since my prof Obrenic sucks at teaching. :)
Thanks!
2024- Still best series so far!
you're an actual hero.
You are amazing thank you so much!!!!!!! Very good explanation :)))
You're very welcome!
thanks for helping me understand this stuff, instant subscribe!
Thanks for the video!
Amazing Explanation !
Also can you tell me the name of the theme playing in your channel intro , it sounded really good !
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.
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 for not having a thick indian accent
looooool
holy crap THANK YOU
Nice explanation
thank you so much for this
Amazing explanation. I bet you a five year old can easily understand CFG by watching this video :-) Thank you!
thaaanks a lot
Where were you when I took theory of computation :(
In your context-free dreams
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, sir :)
You're welcome!
Tnx man😅
Thanks!
Very good video and damn, you're attractive, and so is your voice
Professor, at 4:20 you inserted a comma into the string!
Would this also work as a CFG for PAL?:
S = 0A | 1B | 0 | 1 | E
A = 0 | S0
B = 1 | S1
Would this work for palindromes?
S -> 0 | 1 | E | 0B0 | 1B1, B ->0B | 1B | E
01100 in language but not a palindrome
goated
Can you tell me what’s the name this application you use?
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).
ur so cool....
handsome and smart
I have never hated a class or subject more than this
5 minutes in and i have no idea what you're saying.
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.
intro music is out of time