Pushdown Automaton (PDA) Example: {0^n 1^n}
Вставка
- Опубліковано 23 жов 2020
- Here we derive a PDA for the infamous non-regular language {0^n 1^n : n at least 0}. We give some tips as well for how to solve other PDAs. The general aspect here is to "match" 0s with 1s by pushing 0s onto the stack, and popping the 1s in tandem. There is some complication with popping an empty stack, so we push a "dummy" character on the stack to detect when the matching has concluded to avoid this problem.
What is a pushdown automaton? It is a finite state machine, where on each transition, items can be pushed or popped off of a stack it has, which has unlimited height. See • What is a Pushdown Aut... for more details.
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
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!
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!
Ryan your videos are saving my bacon in my Models of Computation class. You're the man!
great video mate keep going. Much love!!!
Thank you so much. Very clear and exactly what I needed to understand this
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 such a simple and easy to understand video :D
This is a great video. Thank you so much
Incredible explanation
Thanks for the video!
very helpful, thank you :)
Thank you so much!
i stopped mid-video just to say THANK YOU
Thanks!
Thank you Ryan sir😊
Thanks!
great video
Thanks a much!
thank you for the video! it was really helpful.
thank you
Excellent
Thanks
Can you just put up a worksheet kinda thing ,that'll be great i feel
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
so how come no q loop here or thats for cfg
helpful indeed
Glad it helped!
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
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 😛
2 stack pushdown automata?
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.
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.
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!!
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.
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
cheers mate
the other type of PDA would be a lot more fun than this