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!
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 :)
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?
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.
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?
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
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
Its notably harder to teach a class with constant interruptions and questions than to explain it via video.
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
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!
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 :)
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!
This is gold content in such a niche field
thank you for such a simple and easy to understand video :D
Incredible explanation
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
your video helped me a lot! as always!
that triple e transition was good point
thank you.
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
i stopped mid-video just to say THANK YOU
great video mate keep going. Much love!!!
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 😛
Thanks for the video!
This is a great video. Thank you so much
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.
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
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 ❤️
Thank you so much!
Excellent
Thanks
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!!
Thank you Ryan sir😊
Thanks!
so how come no q loop here or thats for cfg
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
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.
very helpful, thank you :)
Thanks!
thank you
great video
2 stack pushdown automata?
Thanks a much!
thank you for the video! it was really helpful.
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.
helpful indeed
Glad it helped!
the other type of PDA would be a lot more fun than this
cheers mate
bro can u solve 4 questions for me rn? I ll pay u