For anyone wondering how the machine knows that it's the middle of the string, it knows that because it's basically trying all possibilities of middle in the string. For each letter read, it assumes that it's already in the middle. When it receives the first letter (a in this case) on the state q2, it goes to both q2 AND q3 (this is allowed since it's a non-deterministic automata). The automata now has two parts, one in the state q2 and other in the state q3. The former will keep receiving new characters until the end of the string and the latter will check if the stuff that's in the stack is equal to the rest of the string, if it is, then your string is a palindrome. In the case of the first 'a', the stack will be empty so the second part of the automata will stop and only the first part will continue. When it receives the first 'b', the stack will have 'ab' and the second part will continue because the rest of the string is 'ba', reaching the end state when the string ends.
**** Bookmark **** 3:33 Meaning of the language 8:04 Tracing of abba 8:54 Midpoint of the even palindrome string 10:46 Tracing of abab - non palindrome string 12:41 Confusion about how to know when we reached the midpoint of the string
Mate, thank you for these videos. My teacher just gave us mathematical notations and formulas and demonstrations, I pretty much didn't understand a single sentence. This thing saved me.
@@marxman1010 Sadly, they are untouchable, it's always the student's fault, you know... Meanwhile, most teachers are just an obstacle between you and a diploma.
@@DarkOceanShark I actually graduated top of the class too! Now I'm doing a master's degree. I got the highest grade in the automata and compilers exam because of these videos.
It's because the epsilon denotes transition without accepting anything. Thus the operation on state q2 and q3 will occur simultaneously. The operation on q3 will fail multiple times until it reaches the mid position of the palindrome(if it is indeed a palindrome) and will reach the final state at least once if it is a palindrome. Just think of how a recursion works [if you are a programmer ; ) ] . All the pop operations are basically taking place on q3 after every update(or push operation) of the string on q2. I know i really suck at explaining things. But I really can't give a better explanation of it ! :3 Btw, superb explanation again sir !!!
I really appreciate your work Neso Academy, its very interesting to learn by ur channel, but its not possible for me to like or comment on each video... But here i wanna say Thanks a lot, ur method of teaching is very good n very effective. I'm able to score good marks 😁😁
I need to know how u designed it what are the steps involved? in each video the diagram just appears out of nowhere and you explain the diagram. I know how to dry run a given diagram i want to be able to make that diagram when a particular language is given!!!!!!
Y'all shouldn't lash out on this guy. I was about to make the same comment..(tho maybe not the way he said it). But, at least the tutor should walk us through the whole thought process of the diagram, rather than the way the complete diagram just appears and then he explains it. This is not to downplay how explanatory his videos are at all. He's a great teacher.
As, you have already mentioned that we will have Non-deterministic PDA, so we just have to think about a single possiblity of approaching final state, so we just looped q1 for both "a" and "b" and for q2, again we have looped the state for both "a" and "b". But for former half of the input string - we are pushing alphabets (a,b) in stack, and for later half - we are popping alphabets from the stack. Since for a string to be accepted, after pushing 'n' alphabets in stack, we must have 'n' popping statements. So that is how, we have accepted only "even strings" (strings having even no. of alphabets). And to attain the palindrome, we have pushed "a" for input "a" and "b" for input "b". That will ensure while popping alphabets in stack that, palindromic sequence must be present in later half of input sequence to get to the final state. Thanks @NesoAcademy.
Thank you for the great lecture. I think it was a good idea to encourage people to disclose their ideas. Many of them are wrong, but at least they are funny.
1. first push Z0 onto stack 2. check the input a or b, if input a push onto the stack or if b do the same. 3. he makes e , e -> e for going to another state. 4. check other inputs, if the input a or b is topmost element of the stack, popped of the stack. 5. e, z0 - > e. popped z0 of the stack. 6. your stack is empty and string is also completed. correct me if i'm wrong. Thank you :)
It is non-deterministic or probabilistic as the even length can be random . The reason is that string lengths are random even numbers. NDPAs can be adjusted through epsilon transition. But, based on this If you were to draw a deterministic PDA, then (a) You wouldn't want to start with a stack bottom symbol $/Zo as it requires an epsilon transition. (b) You may however pop an empty string or in other words pop an epsilon, while pushing a new stack symbol (c) Make the stack empty without and/or reach the final state (d) Also design your deterministic PDA such that the stack can't be emptied for those strings which aren't even palindromes (e) Unfortunately,a one-size-fits-all deterministic PDA is hard to draw in a transition graph if the alphabet consists only of two letters like {a,b}, as epsilon is disallowed as a input symbol AND all the transitions are required to be defined unlike a NPDA. Hence you have to generate Deterministic PDAs for strings of each even length starting from minimum string of length 2(for aa and bb), length 4( aaa,bbbb,abba,baab)...and so on for length 6 to whatever even length you want)
THANKS A LOT !!!!!!!! I was stucked by the problem for almost two weeks when I was reading a book about theory of computation, this vedio really helped me !!!!
To answer quickly, it won't know. It will follow all paths that are still valid, so multiple options will be active because epsilon transitions allow this. Eventually, if it crossed the middle too quickly or too late, it will terminate that option either when it evaluates the stack or doesn't reach a final state. As already mentioned, the next lecture goes into this.
For determining the middle of palindrome , i guess in the question itself it is given that w represent the first half of the string and wr represent the remaining half string .
12:12 we just checked the middle of the stack, just forget that we are constructing a PDA for even palindrome just forgot, you have two conditions to push the number in the stack but at 12:12 the symbol A, we didn't push it because we have to check A,A->E,but at this time why we don't follow the 2nd condition that is B, B->E, because we have B, at topmost in our stack so it may be popped out. at 9:16 we first checked the 2nd condition that is B, B->E, so at 12: 12, why we gave the priority to A, A->E,,,,, if we checked this condition B, B->E, we poped the b in our stack because it is the topmost element ./////
q2 is going to work only when the stack is empty and does not contain any 'a' or 'b' values. Hence, when equation is half complete, there will be an 'a' or 'b' in the stack and hence, system will proceed to q3.
About question: We don't know if we are in the middle of automata, but just go into two directions simontinsly on every input, then it would be checked at the end
Its inherently an NFA, so it tries all possibilities, half is after first symbol and fails, half is after second symbol and succeeds. Coz there exists at least one path that accepts it passes in the case of abba.... In the case of abab it would still fail after second symbol, then try after 3rd i.e and fail and try after last symbol and still fail. With no more possibilities will finally accept defeat and conclude it just will never accept abab.
Ohk! So the thing is a machine cant decide when it is in the middle of a string. Rather it checks as if each character encountered to be the middle of the string. The NULL transition is not to move to Q3 in the middle, rather it is to check for multiple transitions. For each character the PDA undergoes multiple transition, to be specific two transitions, and whichever suits it further, it carries on in that path. NESO Academy is great but these minor mistakes can defy the understanding of students. Please rectify this in the video.
do we have to design the machine as such or will it be given in the question? coz you just go straight away to a machine you have drawn and that leaves a part unattended
Vineet Sharma t24 epsilon just means nothing is the input, being popped or being pushed, in the case it’s just a representation, but it’s not doing anything to the stack.
I am not sure if this PDA is correct. Can you really just ASSUME that we are in the middle of the string? How do we assume it? If someone is running an input string through this PDA given, how do they ASSUME they are in the middle of the string? For those watching this video, the ideas and theory makes sense but do not ASSUME anything because it will be ambiguous to whoever looks at your PDA.
We don't actually need to know when we are in the middle of a string because of the nondeterminism of a PDA. It is like an NFA, where as long as one path of the string leads to an accept state, it will be accepted. The epsilon transition from q2 to q3 allows us to jump to the part of the PDA where we pop symbols at any point, while also staying it q2.
small query! If want to convert a grammer to PDA , should the grammer definately in GNF? cause I have seen other method for convertinng Non- GNF to PDA
for those who are wondering how machine will get to know about the middle, so machine will just guess and that's why here the non-determinism comes into the role.
How many states are required for a given string? Is there any rule for determining beforehand the number of states that will be required to verify if a given string falls within the language? Please explain this.
Do you think your logic is correct. I have a doubt what if the strings start with b then it never be able to proceed because in our case string should always start with a but our language didnot have strings that are just starting with a
this machine will accept strings like "a^n" and "b^n" where n is even integer in example: "aaaaaa" or "bbbbbb" but in Language ww^r is not match with these strings can you explain this pls
In the first case w = aaa and w is more than one sign, in the second case w = bbb and one more w is also more than one sign. Both are even palindromes on the alphabet {a,b}. I think it matches, but maybe I don't understand something.
I understood how do we know that we reached the middle states, firstly the input symbols we used in the transition diagram are all pushed in to the stack and then we can find out we reached to the middle state because all input symbols we used are already pushed and there is nothing to push ,and by reaching the next state we can pop the remaining string and can reach to the final state. Is this true But this is my guess ,after watching this video
It can be like : L= {wcw^r | w=(a+b)^+ } And the mid point of our string would be the transition : c,a/a c,b/b c,z0/z0 means if a or b or z0 is the top most element then dont do anything just cross. Thats what i got from my mind
You are amazing, I was wondering that how machine will be able to identify we have reached the middle part and then you said about the query instantly. That was amazing.
-_- I stopped the video at the palindrome example!! and literally scratched my head for like half an hour!! just to figure out HOW THE HELL THE PDA KNOWS THAT IT IS IN THE MIDDLE OF THE STRING finally when after not getting any answer i decided to just move on assuming that its some stupid mistake!! and right after I played the video it said that I must be having the doubt I had!!!! I realized I wasted my time thinking about that doubt and YOU SHOULD REALLY PUT ATLEAST AN ANNOTATION IN ADVANCE SO WE DON'T WASTE OUT TIME! *so angry right now* BTW thank you very much really appreciate your work HATS OFF! and really grateful to you thanks again!
In the end I guess there was a good side,, bc of the brainstorming and discussing it with my friends.. I will remember this for a long time .. but regardless there should be an annotation at the start of that (doubt) example .
How can you assume by yourself that it has reached to the middle of string, instead there should be a better algorithm to be proposed as u showed in turing machines
Sir, if on Q3 it checks for input 'a' first then in the same way on state Q2 it will check for pushing of input 'a' first always.. Then we'll don't have any even palindrome like 'baab' ?
Yes you're correct. To solve this, just add a, e -> A and b, e -> B to the transition between q2 and q3, that way it wont accept the empty string. He even made mistakes on the video prior to this unfortunately
How I will in the middle of the string ..?? E.g - " aaaa " is the string ..How this will know when to push and when to pop the element from the stack ..???
Every time it reads an input symbol it "guesses" it is i the middle by using the epsilon transition from q2 to q3. This is a non-deterministic machine so a new instance is created where one instance remains on q2 and pushes, and the other instance goes to q3 and pops. If it wasn't in the middle then the new instance will be rejected at some point since no valid transitions would be available and the original instance will remain until it eventually does reach the middle. Its a bit hard to explain but how it help.
The questions in our exam asks us to design a PDA, not to explain a PDA.... You are just explaining a PDA..., From where has this design come from, how can we construct it...??
This design is not ok because how machine will decide processing is at middle of string. Every capabilities must inbuilt with specific state. That is not here so it is wrong. How machine will decide we have to take null from input ant not pop from stack.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
For anyone wondering how the machine knows that it's the middle of the string, it knows that because it's basically trying all possibilities of middle in the string. For each letter read, it assumes that it's already in the middle.
When it receives the first letter (a in this case) on the state q2, it goes to both q2 AND q3 (this is allowed since it's a non-deterministic automata). The automata now has two parts, one in the state q2 and other in the state q3. The former will keep receiving new characters until the end of the string and the latter will check if the stuff that's in the stack is equal to the rest of the string, if it is, then your string is a palindrome.
In the case of the first 'a', the stack will be empty so the second part of the automata will stop and only the first part will continue. When it receives the first 'b', the stack will have 'ab' and the second part will continue because the rest of the string is 'ba', reaching the end state when the string ends.
Just noticed that he explains this in the next lecture. I'll leave this here anyway, maybe it'll help someone.
@Rimack Zelnick apparently every dpda can be converted to npda not vice versa
Thanks 🤞
Thanks
@@edulgl You helped me a lot. I was wondering the middle point. PDA is non-deterministic, so there could be multiple states at the middle point.
**** Bookmark ****
3:33 Meaning of the language
8:04 Tracing of abba
8:54 Midpoint of the even palindrome string
10:46 Tracing of abab - non palindrome string
12:41 Confusion about how to know when we reached the midpoint of the string
NDFA
I do not actually understand how to create the given PDA,just how to check if the PDA is correct or not
Mate, thank you for these videos. My teacher just gave us mathematical notations and formulas and demonstrations, I pretty much didn't understand a single sentence. This thing saved me.
Only one teacher, the best one, is enough. Other teachers must improve their teaching skills, otherwise will lose job in the future.
@@marxman1010 Sadly, they are untouchable, it's always the student's fault, you know... Meanwhile, most teachers are just an obstacle between you and a diploma.
An owl learning about PDA, this is the most random thing I have ever seen 😂
@@DarkOceanShark I actually graduated top of the class too! Now I'm doing a master's degree. I got the highest grade in the automata and compilers exam because of these videos.
It's because the epsilon denotes transition without accepting anything. Thus the operation on state q2 and q3 will occur simultaneously. The operation on q3 will fail multiple times until it reaches the mid position of the palindrome(if it is indeed a palindrome) and will reach the final state at least once if it is a palindrome. Just think of how a recursion works [if you are a programmer ; ) ] . All the pop operations are basically taking place on q3 after every update(or push operation) of the string on q2.
I know i really suck at explaining things. But I really can't give a better explanation of it ! :3
Btw, superb explanation again sir !!!
this is an incredible explanation, i wasn't able to pick up on this before. thanku sm!!
You heard the question of my heart...lots of love ❤️
I really appreciate your work Neso Academy, its very interesting to learn by ur channel, but its not possible for me to like or comment on each video...
But here i wanna say Thanks a lot, ur method of teaching is very good n very effective. I'm able to score good marks 😁😁
I need to know how u designed it what are the steps involved? in each video the diagram just appears out of nowhere and you explain the diagram. I know how to dry run a given diagram i want to be able to make that diagram when a particular language is given!!!!!!
Don't be so rude. Please watch previous videos man.
You have to figure it out using your working brain, using the information given in earlier videos. Please respect the efforts of the video maker.
Y'all shouldn't lash out on this guy. I was about to make the same comment..(tho maybe not the way he said it).
But, at least the tutor should walk us through the whole thought process of the diagram, rather than the way the complete diagram just appears and then he explains it.
This is not to downplay how explanatory his videos are at all. He's a great teacher.
@@thestar001Officialwell yes
Should explain how the diagram is created
As, you have already mentioned that we will have Non-deterministic PDA, so we just have to think about a single possiblity of approaching final state, so we just looped q1 for both "a" and "b" and for q2, again we have looped the state for both "a" and "b".
But for former half of the input string - we are pushing alphabets (a,b) in stack, and for later half - we are popping alphabets from the stack.
Since for a string to be accepted, after pushing 'n' alphabets in stack, we must have 'n' popping statements. So that is how, we have accepted only "even strings" (strings having even no. of alphabets).
And to attain the palindrome, we have pushed "a" for input "a" and "b" for input "b". That will ensure while popping alphabets in stack that, palindromic sequence must be present in later half of input sequence to get to the final state.
Thanks @NesoAcademy.
Exactly same question arise in my mind 13:28 . Even I feel that you are going wrong 😅 but now everything is clear.
Thank you for the great lecture. I think it was a good idea to encourage people to disclose their ideas. Many of them are wrong, but at least they are funny.
????
Thank You Mam!
I really liked your explanation 🔥🔥.
Keep it up,NesoAcademy👍👍
1. first push Z0 onto stack
2. check the input a or b, if input a push onto the stack or if b do the same.
3. he makes e , e -> e for going to another state.
4. check other inputs, if the input a or b is topmost element of the stack, popped of the stack.
5. e, z0 - > e. popped z0 of the stack.
6. your stack is empty and string is also completed.
correct me if i'm wrong. Thank you :)
"but how would we know that we reach the mid point" this was the question that got my teacher and she said she will look into it.
lol, how do such teachers get degree in the first place
It is non-deterministic or probabilistic as the even length can be random . The reason is that string lengths are random even numbers. NDPAs can be adjusted through epsilon transition. But, based on this If you were to draw a deterministic PDA, then (a) You wouldn't want to start with a stack bottom symbol $/Zo as it requires an epsilon transition. (b) You may however pop an empty string or in other words pop an epsilon, while pushing a new stack symbol (c) Make the stack empty without and/or reach the final state (d) Also design your deterministic PDA such that the stack can't be emptied for those strings which aren't even palindromes (e) Unfortunately,a one-size-fits-all deterministic PDA is hard to draw in a transition graph if the alphabet consists only of two letters like {a,b}, as epsilon is disallowed as a input symbol AND all the transitions are required to be defined unlike a NPDA. Hence you have to generate Deterministic PDAs for strings of each even length starting from minimum string of length 2(for aa and bb), length 4( aaa,bbbb,abba,baab)...and so on for length 6 to whatever even length you want)
Not any in the world like you sir very nice
THANKS A LOT !!!!!!!! I was stucked by the problem for almost two weeks when I was reading a book about theory of computation, this vedio really helped me !!!!
How will the machine know we have reached the middle of the stack?
It is in the next lecture.
see 13:11
To answer quickly, it won't know. It will follow all paths that are still valid, so multiple options will be active because epsilon transitions allow this. Eventually, if it crossed the middle too quickly or too late, it will terminate that option either when it evaluates the stack or doesn't reach a final state. As already mentioned, the next lecture goes into this.
That’s becoz this is non-deterministic pda. So there are multiple way to reach and ultimately it will accepted at the end.
Who is the teacher for the automata series? I like him and his teaching style: structured, gradual.
Exactly he is so precise and clear
nice explanation love from chandigarh university 🦋🦋❤❤
your teching technique is extraordinary thanks lot
For determining the middle of palindrome , i guess in the question itself it is given that w represent the first half of the string and wr represent the remaining half string .
The above PDA works fine only with w = (a+b)* not with (a+b)^+
agree
Not a completely generalized solution !
true
Yes because he assumed reaching mid point on q2 state with blank input. But without assuming anything can't we do this with PDA?
no dude. (a+b)* includes epsilon, which is odd in itself. Hence, (a+b)* removes the palindromes of odd probability completly. Say if I am wrong.
12:12 we just checked the middle of the stack, just forget that we are constructing a PDA for even palindrome just forgot, you have two conditions to push the number in the stack but at 12:12 the symbol A, we didn't push it because we have to check A,A->E,but at this time why we don't follow the 2nd condition that is B, B->E, because we have B, at topmost in our stack so it may be popped out.
at 9:16 we first checked the 2nd condition that is B, B->E, so at 12: 12, why we gave the priority to A, A->E,,,,, if we checked this condition B, B->E, we poped the b in our stack because it is the topmost element ./////
The input is a and you check for b 🤓??
q2 is going to work only when the stack is empty and does not contain any 'a' or 'b' values. Hence, when equation is half complete, there will be an 'a' or 'b' in the stack and hence, system will proceed to q3.
Thanks for the vid, saving my life.
in case of abab if i choose to input b instead of a at q3 then i should be able to pop b from stack.. then why is it not considered?
exactly my question
I don't see how that pda is for (a+b)^+ and not for (a+b)^* because it accepts the empty string too
yeah man, same doubt
@@A_Myth963 epsilon is a 0 len string. 0 is even hence accepted
I like this channel
what an explanation sir woowww simply awesome 👏👏👏👏👏 thank you so much 😇
you re an excellent teacher !!!! better than my lecturer anyway
You said (at 3:17) positive closure means it must not contain empty symbol or €, but your PDA design has €mpty symbol
€ has a different reason here. It means no element is popped from the stack.
Pls go thru the previous 2 lectures for better understanding.
@@Uniquevibers944 but it still accepts epsilon as an input you can check it if you want,and that shouldn't be possible
About question: We don't know if we are in the middle of automata, but just go into two directions simontinsly on every input, then it would be checked at the end
in this string abaaba : I think in the state q2 we have to add a,epsilen,b and b,epsilen,a to our state q2
NO 🙅♂ LEMON 🍋NO 🙅♂ MELON 🍉
It should accept "abab" as well?
No, it should not accept because the reverse order is totally different from the actual order
abab→baba not again as abab
How will it whether it reached the mid point of the stack?
13:28
Vocabulary and accent are awesome
Are you joking? His vocabulary is actually terrible.
I watched about all video sirr nice Experience & thanks a lot
you should have draw the state diagram step by step... that would lot easier to understand ☺☺
Isn't this PDA supposed not to accept epsilon string since language is positive closure? but it seems it's accepting empty string too?
that's what I thought
Its inherently an NFA, so it tries all possibilities, half is after first symbol and fails, half is after second symbol and succeeds. Coz there exists at least one path that accepts it passes in the case of abba....
In the case of abab it would still fail after second symbol, then try after 3rd i.e and fail and try after last symbol and still fail. With no more possibilities will finally accept defeat and conclude it just will never accept abab.
Ohk! So the thing is a machine cant decide when it is in the middle of a string. Rather it checks as if each character encountered to be the middle of the string. The NULL transition is not to move to Q3 in the middle, rather it is to check for multiple transitions. For each character the PDA undergoes multiple transition, to be specific two transitions, and whichever suits it further, it carries on in that path. NESO Academy is great but these minor mistakes can defy the understanding of students. Please rectify this in the video.
thanq you so much
hmm how will a machine know it is in the middle of something !
Well check the next tutorial... there is a better form of representation :)
even my teacher studies from neso academy....so we have no other choice but to studies some wrong concepts to score marks in the examination
hmm, you did not watch the whole video did you
do we have to design the machine as such or will it be given in the question? coz you just go straight away to a machine you have drawn and that leaves a part unattended
this machine is also accepting epsilon as an input which is not in language .
Vineet Sharma t24 epsilon just means nothing is the input, being popped or being pushed, in the case it’s just a representation, but it’s not doing anything to the stack.
YARIN FİNALİM VAR KONUYU ÖĞRENDİM ALLAH RAZI OLSUN
Video starts at 4:19
Does this implementation accept empty strings by reading only epsilons?
how minimum 1 letter property is implemented in this PDA?
for this question if we push for every 2 different elemtn and pop for different element isnt it a better and easier answer
Thank you..
I am not sure if this PDA is correct. Can you really just ASSUME that we are in the middle of the string? How do we assume it? If someone is running an input string through this PDA given, how do they ASSUME they are in the middle of the string? For those watching this video, the ideas and theory makes sense but do not ASSUME anything because it will be ambiguous to whoever looks at your PDA.
We don't actually need to know when we are in the middle of a string because of the nondeterminism of a PDA. It is like an NFA, where as long as one path of the string leads to an accept state, it will be accepted. The epsilon transition from q2 to q3 allows us to jump to the part of the PDA where we pop symbols at any point, while also staying it q2.
key point : as long as one path of the string leads to an accept state, it will be accepted.
we are dumbos we dont have any idea how u did this but this would be probably my last time seeing this lecture #endSemsAreHere
@Vinayak Ojha Haan bhai job bhi lg gyi 😌
@Vinayak Ojha JP Morgan 😄
@Raja Shashank bhai referral daal dun tera ?
@@ishaankanwar5316 brother any suggestions for juniors
@@ishaankanwar5316 bhai party pending 🌚
I think we can just know middle by scanning the string and diving by 2so knwo I can move to next state n/2+1 element?
Thanks, very helpful!
small query! If want to convert a grammer to PDA , should the grammer definately in GNF?
cause I have seen other method for convertinng Non- GNF to PDA
These are really good tutorials. Keep it up!
Great tutorial!
for those who are wondering how machine will get to know about the middle, so machine will just guess and that's why here the non-determinism comes into the role.
Good question. How we find out it is in midway?
It will work for empty string as well right?
how will the machine know, if it's reached at the middle, so as to pass Epsilon???
Okay? But then there is midpoint if it is even. What if it is an odd symbol? Like RACECAR? what should I assume the midpoint is?
How many states are required for a given string? Is there any rule for determining beforehand the number of states that will be required to verify if a given string falls within the language? Please explain this.
Do you think your logic is correct. I have a doubt what if the strings start with b then it never be able to proceed because in our case string should always start with a but our language didnot have strings that are just starting with a
Sir, but u didn't taught how to design the PDA.
SIr, DPDAs are realistic, we can construct a machine but where as NPDA not. If we are not able to convert from NPDA to DPDA what is the use of NPDA
what is this ??? anyone let know yar i never get the point , anyone if have idea please give me response???
11.53 how do we know whether we have reached the mid point of the string ?
yeah that makes no sense at all you can't just assume
this machine will accept strings like
"a^n" and "b^n" where n is even integer
in example: "aaaaaa" or "bbbbbb"
but in Language ww^r is not match with these strings can you explain this pls
In the first case w = aaa and w is more than one sign, in the second case w = bbb and one more w is also more than one sign. Both are even palindromes on the alphabet {a,b}. I think it matches, but maybe I don't understand something.
Can I get a vdo for accepting all the plaindrome
I understood how do we know that we reached the middle states, firstly the input symbols we used in the transition diagram are all pushed in to the stack and then we can find out we reached to the middle state because all input symbols we used are already pushed and there is nothing to push ,and by reaching the next state we can pop the remaining string and can reach to the final state.
Is this true
But this is my guess ,after watching this video
It can be like :
L= {wcw^r | w=(a+b)^+ }
And the mid point of our string would be the transition :
c,a/a
c,b/b
c,z0/z0
means if a or b or z0 is the top most element then dont do anything just cross.
Thats what i got from my mind
Nice....plz Upload fast more videos
You are amazing, I was wondering that how machine will be able to identify we have reached the middle part and then you said about the query instantly. That was amazing.
Thankyou sir
is it work for odd palindroms? (aba i guess)
-_- I stopped the video at the palindrome example!! and literally scratched my head for like half an hour!! just to figure out HOW THE HELL THE PDA KNOWS THAT IT IS IN THE MIDDLE OF THE STRING finally when after not getting any answer i decided to just move on assuming that its some stupid mistake!! and right after I played the video it said that I must be having the doubt I had!!!! I realized I wasted my time thinking about that doubt and YOU SHOULD REALLY PUT ATLEAST AN ANNOTATION IN ADVANCE SO WE DON'T WASTE OUT TIME! *so angry right now*
BTW thank you very much really appreciate your work HATS OFF! and really grateful to you thanks again!
In the end I guess there was a good side,, bc of the brainstorming and discussing it with my friends.. I will remember this for a long time .. but regardless there should be an annotation at the start of that (doubt) example .
Same after 6 years
How can you assume by yourself that it has reached to the middle of string, instead there should be a better algorithm to be proposed as u showed in turing machines
How to design the PDA pls explain?
It's 5 year old video for your info
Sir, if on Q3 it checks for input 'a' first then in the same way on state Q2 it will check for pushing of input 'a' first always..
Then we'll don't have any even palindrome like 'baab' ?
But how can i construct this machine ?
pda explanation does not satisfying,improvement is needed
assume kar bhai
How do PDA knows that the middle of the string is reached?
how pda knows we are at middle of string?
Great video! But isn't this NPDA accepts the empty string while it was a condition that the word set cannot be empty?
Yes you're correct. To solve this, just add a, e -> A and b, e -> B to the transition between q2 and q3, that way it wont accept the empty string. He even made mistakes on the video prior to this unfortunately
@@STxFTW we just add a state q such q2-->q for a,b input then q -->q3 for € input
how this NPDA will Determine it is at the center of the String ???
it doesn't know , it guesses
How I will in the middle of the string ..??
E.g - " aaaa " is the string ..How this will know when to push and when to pop the element from the stack ..???
Every time it reads an input symbol it "guesses" it is i the middle by using the epsilon transition from q2 to q3. This is a non-deterministic machine so a new instance is created where one instance remains on q2 and pushes, and the other instance goes to q3 and pops. If it wasn't in the middle then the new instance will be rejected at some point since no valid transitions would be available and the original instance will remain until it eventually does reach the middle. Its a bit hard to explain but how it help.
how to check middle position of string
nice video
The questions in our exam asks us to design a PDA, not to explain a PDA.... You are just explaining a PDA..., From where has this design come from, how can we construct it...??
Guys he explained everything in next part....
Nice
This design is not ok because how machine will decide processing is at middle of string. Every capabilities must inbuilt with specific state. That is not here so it is wrong. How machine will decide we have to take null from input ant not pop from stack.
Dude this is a NPDA design not a DPDA
it's for us humans
if you want the machine to understand it you must covert it to DPDA :)
what about the odd palindrome there exist's no middle
palindrom harici örnek niye çözmemişsiniz?
length of input/2 is the mid point
Still how many videos left to complete the course, please reply. And in how many days you expect to complete the course?
pop=lift if there, push=drop
In both states q2 and q3,top of stack will be compared if we get epslon then we consider state q2 else we go to state q3