Even my Lecturer named Sir PSS won't and never explain this correctly ( he won't explain to us ). But thanks you did it. Just cover my confused on these things only in 11 minutes cap. Big thanks from Indonesia :)
Indeed, awesome explanation in a very short time is an art! recording date of this video tells me I am super lucky to have such rich resource on the exact time! Thank you Ryan!
Thank you for these videos! They're really helpful for me to understand theory of computation. The amazing work you're doing it helping out many students!
if the stack needs to be empty to be accepted, why the need for the $ symbol, even without the $ symbol if the input will only finish if there are as many (or more) 1's to 0's and the stack will only empty if there are as many (or more) 0's to 1's so the number of 0's and 1's will need to be the same and no $ should be needed?
Would q0 also be an accept state since 0^n1^n can be an empty string? I know that the empty string is able to go through every state, but I'm just curious if it's appropriate to also make q0 an accept state.
@@EasyTheory Okay. Just making sure cuz my professor is a hardass and will probably take credit away for something like that lol. Thanks for the video! Very helpful.
stupid question but here it goes: If we wanted could we pop off all the 1's at q2, but twice as fast? Meaning if I wanted to have 0^n and 1^2n, could i just have the same thing as your pda, but instead at q2, pop off (11,0) instead of (1,0)? Thank you so much for your tutorials! they are amazing.
No such thing as a stupid question if you really want to know the answer :) Yes, but only if the language is {0^n 1^(2n) : n at least 0}. If you wanted to apply this to {0^n 1^n : n at least 0} (note the difference in the 1 exponent), then this won't work whenever the input string has n being odd. But if you instead insisted that n be even, then yes you could. The only "problem" is that the PDA definition only allows one character to be read/popped/whatever in one transition. You can augment the definition to an "extended" PDA, where more than one can occur at once. This is usually done on the stack, not the input though. And thanks for watching!
Hey, I keep following the automaton you drew to verify that it rejects "10". But it keeps landing on the accepting state q3. Am I doing something wrong? Stack: [], String: "10", State: q0 Stack: [$], String: "10", State: q1 Stack: [$], String: "10", State: q2 Stack: [], String: "10", State: q3 (accepting) Or do you have to exhaust the entire input string for it to accept?
You can't take that transition because look at what is required to pop off the stack in order to take it? You must be able to pop off the $ symbol from the stack but...the $ is not at the top of the stack! A 0 will be on the top of the stack after you have read all the 0s and all the 1s in the case of there being more 0s than 1s. So yes, epsilon can be read but you cannot pop something off the stack if it is not at the top of the stack.
Even my Lecturer named Sir PSS won't and never explain this correctly ( he won't explain to us ). But thanks you did it. Just cover my confused on these things only in 11 minutes cap. Big thanks from Indonesia :)
Explains in 10 minutes what my professor took two hours to skim over, thank you!
I wouldn't discount another professor that easily, but thanks anyway!
@@EasyTheory HARRIS 2024
@@KarenWasherGrudzien TOC> politics
This is gold content in such a niche field
Indeed, awesome explanation in a very short time is an art! recording date of this video tells me I am super lucky to have such rich resource on the exact time! Thank you Ryan!
Thanks
finally something my brain could wrap around . bets explanation and easy way thank you .
Ryan your videos are saving my bacon in my Models of Computation class. You're the man!
that triple e transition was good point
thank you.
thank you so so much! I don't pay attention in class and just look for your video on the topic before the quiz and I've passed all of them
Thank you for these videos! They're really helpful for me to understand theory of computation. The amazing work you're doing it helping out many students!
Thanks very much!
i stopped mid-video just to say THANK YOU
if the stack needs to be empty to be accepted, why the need for the $ symbol, even without the $ symbol if the input will only finish if there are as many (or more) 1's to 0's and the stack will only empty if there are as many (or more) 0's to 1's so the number of 0's and 1's will need to be the same and no $ should be needed?
that way we would not know that the PDA's stack is empty. It's like putting a slab over void to ensure that we're standing on rock bottom 😛
Can you just put up a worksheet kinda thing ,that'll be great i feel
Thank you so much. Very clear and exactly what I needed to understand this
Incredible explanation
thank you for such a simple and easy to understand video :D
great video mate keep going. Much love!!!
Would q0 also be an accept state since 0^n1^n can be an empty string? I know that the empty string is able to go through every state, but I'm just curious if it's appropriate to also make q0 an accept state.
It can, but no need, since there is a way for empty input to make its way through the machine as-is.
@@EasyTheory Okay. Just making sure cuz my professor is a hardass and will probably take credit away for something like that lol. Thanks for the video! Very helpful.
@@charlesroseman9466 lol
@charlesroseman9466 hahaha bro you asked my question.
And also my prof wants to write exactly what is taught haha 😂
@@EasyTheory Thanks for the explanation ❤️
This is a great video. Thank you so much
Thanks for the video!
stupid question but here it goes: If we wanted could we pop off all the 1's at q2, but twice as fast? Meaning if I wanted to have 0^n and 1^2n, could i just have the same thing as your pda, but instead at q2, pop off (11,0) instead of (1,0)? Thank you so much for your tutorials! they are amazing.
No such thing as a stupid question if you really want to know the answer :)
Yes, but only if the language is {0^n 1^(2n) : n at least 0}. If you wanted to apply this to {0^n 1^n : n at least 0} (note the difference in the 1 exponent), then this won't work whenever the input string has n being odd. But if you instead insisted that n be even, then yes you could.
The only "problem" is that the PDA definition only allows one character to be read/popped/whatever in one transition. You can augment the definition to an "extended" PDA, where more than one can occur at once. This is usually done on the stack, not the input though.
And thanks for watching!
@@EasyTheory Many thanks for your answer and even more thanks for putting out such great content!!
Can you do both loops for 1 and 0 on the same state? Or do you have to have a seperate state to do each
Hey, I keep following the automaton you drew to verify that it rejects "10". But it keeps landing on the accepting state q3. Am I doing something wrong?
Stack: [], String: "10", State: q0
Stack: [$], String: "10", State: q1
Stack: [$], String: "10", State: q2
Stack: [], String: "10", State: q3 (accepting)
Or do you have to exhaust the entire input string for it to accept?
yes he said that at the end, the entire input has to be read in order for it to be able to accept.
why do # of 0s and 1s need to be equal?
That's the definition of the language we are working with. So that's kind of a given, and we're just designing a machine that recognizes that language
9:02 why can't you take that transition? You have read the whole input and it is trying to read epsilon.
You can't take that transition because look at what is required to pop off the stack in order to take it? You must be able to pop off the $ symbol from the stack but...the $ is not at the top of the stack! A 0 will be on the top of the stack after you have read all the 0s and all the 1s in the case of there being more 0s than 1s.
So yes, epsilon can be read but you cannot pop something off the stack if it is not at the top of the stack.
Excellent
Thanks
Thank you so much!
Instead of that E-transition b/w q1 & q2 ,
Can we make the initial state final & write that transition as *1,0->E* ?
then you wouldn't be able to pop $ sign. Which is on stack.
@@zahidgul5811 the $ isn't on the stack at q0. Its onlt on the stack after you go to q1.
Yes. That is how the PDA for this language is shown in the textbook I am using.
Thank you Ryan sir😊
Thanks!
so how come no q loop here or thats for cfg
2 stack pushdown automata?
Thanks!
very helpful, thank you :)
thank you
great video
the other type of PDA would be a lot more fun than this
helpful indeed
Glad it helped!
Thanks a much!
thank you for the video! it was really helpful.
cheers mate
bro can u solve 4 questions for me rn? I ll pay u