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!
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 !
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.
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
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
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 way you teach is so good!!!!
that's great, you're making Autumata much more interesting.
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.
The best lesson's creator for this subject
Please decrease the amount of adds this is so annoying!!!!!
Thanks for the video man, it's really helpful
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 ;)
This was so helpful! Thank you!!
You're very welcome!
Bro you just saved my exam thanks!
you're an actual hero.
Thank you for the video! It really helps out since my prof Obrenic sucks at teaching. :)
Thanks!
thanks for helping me understand this stuff, instant subscribe!
2024- Still best series so far!
Amazing explanation. I bet you a five year old can easily understand CFG by watching this video :-) Thank you!
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.
You are amazing thank you so much!!!!!!! Very good explanation :)))
You're very welcome!
Thanks for the video!
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.
holy crap THANK YOU
thank you so much for this
Amazing Explanation !
Also can you tell me the name of the theme playing in your channel intro , it sounded really good !
Nice explanation
thank you for not having a thick indian accent
looooool
Great video! Do you maybe have video on generation trees and Lukasiewicz notation? It's in the CFG chapter of Cohen's book
thaaanks a lot
Thanks!
Thank you, sir :)
You're welcome!
Where were you when I took theory of computation :(
In your context-free dreams
Very good video and damn, you're attractive, and so is your voice
Tnx man😅
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
Professor, at 4:20 you inserted a comma into the string!
Can you tell me what’s the name this application you use?
Would this work for palindromes?
S -> 0 | 1 | E | 0B0 | 1B1, B ->0B | 1B | E
01100 in language but not a palindrome
goated
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....
5 minutes in and i have no idea what you're saying.
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.