Pushdown Automata (Graphical Notation)
TOC: Pushdown Automata (Graphical Notation)
Topics Discussed:
1. Graphical notation of pushdown automata
2. input symbol
3. Pop and push symbols
4. Example of PDA construction
Contribute: www.nesoacademy.org/donate
Website ► www.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...
Пікірлер: 185
Believe me, with the very same language, your explanation is a way better than most people in here. Thank you!
Such a great lesson. Clear, patient, concise and to the point. Good work you guys!
You saved my life, I just wanted you to know !
@angshumansarma2836
4 жыл бұрын
legend
@sagesy9774
3 жыл бұрын
ye pyaar nahi toh aur kya hai
@Jerdz
3 жыл бұрын
@@sagesy9774 I do not understand your language
@sagesy9774
3 жыл бұрын
@@Jerdz nothing it was a silly joke
@sam_682
3 жыл бұрын
@@Jerdz he meant "if this isn't love then what else can it be"
Netflix: Ughh. Neso: Aah
I think for this PDA, q1 must be a final state, as language also accepts that strings for n=0. And also to accept a string, both conditions must be true: 1. Final state must be reached. 2. Stack must be empty. If any of these conditions come false, then string will not be accepted. Apart this, @NesoAcademy, you are providing a great content. Thanks a lot.
@lifeofsreeh
2 жыл бұрын
No , that case every string will be accepted Edit : The right way is to add a transition from q1 to q4
@DFULTCDS
2 жыл бұрын
It's a NFA so what's why there isn't that transition.
@nitigyajoshi4658
2 жыл бұрын
there are two types of acceptance by pda. 1. acceptance by final state 2. acceptance by empty stack
@hemantdewpal1612
Жыл бұрын
correct but I think the mistake is in the question, where the condition should be n > 0.
@kriskurti7497
Ай бұрын
@@lifeofsreeh no, because the initial state is reached only by reading the empty string. No way every string will be accepted if you make q1 a final state
Real heroes don't wear capes
Great job on explaining this. Very explicit and clear for understanding.
Thanks for these lectures. Your explanations are always very clear
Thank you so much for your videos!!! You are wonderful at delivering this material!!
LEGENDARY Explanation...💯
this is just exactly what I needed, thank you so much
1:07 Meaning of a, b -> c 3:24 Example
U are a lifesaver man! Much Love
Thanks a lot, very helpful tutorial!
omg you cleared PDA concept in one shot amazing man
You saved me..!!!! Thank you so much for making such a great content..❤️👍
i wish i see your photo one day, what a nice guy
I swear you're such a life saver! Amazing job
SEHR HILFREICH UND TOLL VIDEO. DU BIST WUNDERBAR MENSCHEN!!!!
Wonderful explanation!
I been wanting to say this, the people behind Neso thanks alot for providing such quality content. I often dont listen to class so its because of you guys I have able to pass subjects like EEE and digital system last year and I still use this to learn for my classes even now. Much appreciated :D
Awesome Videos, He explains everything slowly and clearly.
Thank you so much, great teacher.
In the PDA , transaction from q2 and q3 should be E,E-->E(E= empty transaction) because it should accept the case where n=0and the given PDA will work when n>=1
@utsavpathak2122
Жыл бұрын
where n = 0 the stack will be empty so it will also be accepted
@jriveros3901
8 күн бұрын
Yeah much people coment that
super explanations sir i like very much ....keep going on
best video on the topic out there
After watching this video for over 15 times consecutively...I have understood PDA succesfully...:)
As always nailed it.
This was very helpful!
Good explanation sir
Always the best ,keep up sir!
@yourdailyfails1
3 жыл бұрын
dude your name took over my screen i thought i got fault in my monitor
thank you, good lesson.
really useful content thank you very much
Amazingly helpful
sending soooooooooooo much love your way man your videos are awesome :)
This guy is a hero.
Have my university exam tomorrow Learnt a lot from your lectures Thank you
Wonderful explanation sir jiiiii
What an excellent video. Incidentally, the diagram accounts for n> 0. In order to account for n = 0, do we need an epsilon transition from q2 to q3? -- Best regards and thank you again!
Perhaps I misread it, but it seems like this PDA makes {0^n1^n | n>0}, not {0^n1^n | n>=0}
@frostbite585
6 жыл бұрын
I think you're right
@OmranAlHadad
6 жыл бұрын
his work is correct if he put accept state on "q1"
@GrimstboritH
6 жыл бұрын
yes.
@vaibhavmourya65
5 жыл бұрын
but this will also be true for 000011 as he said one of the condition should satisfy but i feel both should satisfy reaching Z and final states what say
@sahilsaini2764
5 жыл бұрын
Yeah u r right
Nice explanation
a real hero just that...
Such a great line that two conditions for acceptance of any string in pushdown automata is : First: reaching the final state Second:stack should be empty
Thank you sir
Thanks a lot!
I love your videos. I am subscribing.
E, E -> Zo (E: input symbol, E: to be popped -> Zo: to be pushed)
Awesome explanation I m lovin it
@ricaspinto
3 жыл бұрын
McFlurry Sir
@DarkOceanShark
2 жыл бұрын
@@ricaspinto 😭🤣
hi there, thanks a ton on the amazing lecturee, they saved my life. Just a little feedback on something than can make it easier for the viewers. If you number the lectures for each topic, it would be easier to track which video follows from which as youtube doesn't always bring them in sequence.
@brahamaggarwal1800
2 жыл бұрын
you can always watch the whole playlist..... you will get all 112 videos in sequence.
@sjhuz01
Жыл бұрын
@@brahamaggarwal1800 - They're not in the correct order. The "Context-Free Grammar" video references "previous videos" about PDAs when defining what a Context-Free Grammar is. But in the playlist those are #65-84, where this discussion of PDAs starts at #85. ... It is a bit circular anyway, as the Intro PDA video describes them as a way to describe Context-Free Grammar/Language.
Amazing
amazing
Thank you
Perfectoooo.I love you guys :)
a small piece of advice, can you also add the title with the number of the course like the main picture of the video. then it would be much easier for me to know which tutor I am at now. thanks!
thank you
thanks a lot
Q1 should be a final state as well for the n=0 (case ε)
@lukaspovilonis210
6 жыл бұрын
Wolff or replace the transition from q2 to q3 with e, e->e.
@sayantaniguha8519
2 жыл бұрын
@@lukaspovilonis210 Then 00111 will also be accepted na ?
transaction from q2 and q3 should be E,E-->E(E= empty transaction) because it should accept the case where n=0
Hope every university can hire such a teacher to give lectures so that his students don't go to youtube university🙂
Awesome
thx it helps
i can not afford to buy paid your course. i am in 3rd sem now btech. pleaseeeeee dont remove these lectures. its is extremely helpfull
sir in this lecture how to accept empty string? because n>=0 so, it must be accepted. kindly explain in above PDA.
you set n equal 0, so epsilon should be accepted too, right? How does the automata also accept only the epsilon?
You are doing the work of God. Whatever God is or however many Gods there are ... you are doing the work of the good. Thank you kindly, sir, from a dumb American.
@sghqz
4 жыл бұрын
🥰🥰🥰
Thankyou sir
thanks
Superb
your goatted 💯💯💯
sir you are super
@ricaspinto
3 жыл бұрын
yes
for q2 to q3 why don't we use ∑ , ∑ -> ∑ that way 00111 wouldn't be accepted?
The base case for the diagram for 0^n 1^n is not right because it should be n >= 1. If it was n = 0, then it would take the empty string.
What will be happened in case of null string ? As the condition is also true for n=0 then the state q1 should also be accepted if i don't make mistake.
@lucasdarianschwendlervieir3714
5 жыл бұрын
Then the first transition will accept no input and push z_0 to the stack. To make any progress any other transition will need to accept no input, otherwise the empty string is sure to be rejected.
Does the 1s given as inputs get read in the string even if they don't push and pop out of the stack??????.
if n=0 then epsilon in is L which means q1 also needs to be an accept state.
Thanks a lot for the video. What happens when the string "1" is the input? At state q2, it will read 1 but the stack does not have a 0. Will this get rejected?
@abhishekshah5961
5 жыл бұрын
yes! as the number of 0s is not equal to the number of 1s
Why did we pushed down Os into stack but not 1 ?
How about if n = 0 in this example?
What about when q3 reads 0, can we do 0,E->0 and move to q2 state? For example in 001011 while reading 4th input symbol
@frostbite585
6 жыл бұрын
This grammar implies that the language is strictly n number of 0's followed by n number of 1's. There is no mixing of symbols.
How null string will be satisfied in this example . Please explain
You have solved it for n>=1 as final state is at the end, but in the question n>=0 has been mentioned.
but this will also be true for 000011 as he said one of the condition should satisfy but i feel both should satisfy reaching Z and final states what say
@jorgerios3635
5 жыл бұрын
w = 000011 is not accepted by the PDA of the example. Why? After inserting the chain w, the stack contains 00z_0.
I don't understand what was the use of stack in this case? Why all the pushes and pops?
Finally PDA Concept is clear
The example is NOT correct because 'n' is greater or equal to zero. Meaning if n = 0, the string will be empty. In this case, you cannot reach the accepting state (final state) if the string is empty. Correct me if I'm wrong.
everytime i watch video untill the end i always feel that what happened to my laptop screen how come so many scratches? and then realize ohh its in the video
on State q2 why 0,0 --> 0 not mentioned
How to select transition states
You have drawn 4 States, 2 inputs means 3 state must be there
what if it was 1010 what will we do after reaching q3 for 0 input
if the string is 01 then it will not reach the final state...but it should...then what to do?
how a null string will be accepted by this generated PDA?
Is (0^n1^n, where n>=0) possible using an FSM?
@sohaibfazal6528
5 жыл бұрын
No pumping lemma states it is non regular
Great videos! ..but maybe shorten them? 4:30 - 6:30 a 2 min explanation of Zo.
damn you are the first brown boi that i can listen to when it come to youtube learning. keep doing!
in final stage between q3 and q4, what happens if z0 is not in the top the stack?
@backslash8874
5 жыл бұрын
It won't get accepted, as the pop operation will fail !
How to find the transition function..? i mean how you can find that now it will push and now it will pop..?
@afzalozil9734
6 жыл бұрын
see the video from the start there are instructions and rules that determine when an element is pushed and pop...
will null string be accepted?
@ebd1057
6 жыл бұрын
I don't think so in his example, with a null string, you will enter in the first transition and push Z0 to the stack, but you won't enter in the second so you won't reach the accepting state, nor will have an empty stack
@tanuj1253
6 жыл бұрын
I think making q1 as final state also will make sure null string gets accepted. Not sure tho.
Please tell, when will this course complete? Still how many videos left?
@ricaspinto
3 жыл бұрын
Sir i still no know what will the course complete. Courses cant complete things SIR WHY Thanyou!
SIR IF YOU CAN TELL HOW THE TRANSITION TABLE IS MADE
@ricaspinto
3 жыл бұрын
...yes? If he can tell you what will you do??? What will happen!!?? SIR PLEASE explain Thakyou