Pushdown Automata Example - Even Palindrome (Part 1)

TOC: Pushdown Automata Example - Even Palindrome (Part 1)
Topics Discussed:
1. Construction of PDA that accepts even palindromes over the symbols {a,b}
2. Palindromes
3. Palindrome examples
4. Even and odd palindromes

Music:
Axol x Alex Skrindo - You [NCS Release]

[edulgl]

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.

[preetamprag]

I do not actually understand how to create the given PDA, just how to check if the PDA is correct or not

[vivekvasudevan]

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)

[mdsakif]

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...??

[manikantsharma]

How m/c will know center has been reached? This string as you take in example is accepted by non deterministic PDA. First get your concept right then make video.

[nileshthakur]

sir does ur videos have full automata theory syllabus? and discrete mathematical structures?

[summussaer]

I don't see how that pda is for (a+b)^+ and not for (a+b)^* because it accepts the empty string too

[hadipawar]

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

[kidcoder]

How will the machine know we have reached the middle of the stack?

[ishaankanwar]

we are dumbos we dont have any idea how u did this but this would be probably my last time seeing this lecture #endSemsAreHere

[MohdAdnan-qsth]

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 😁😁

[backslash]

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 !!!

[soimtheowl]

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.

[ooltra]

Who is the teacher for the automata series? I like him and his teaching style: structured, gradual.

[SHEETALSHARMA-tzsm]

**** 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

[LordSarcasticVlogger]

Thank You Mam!
I really liked your explanation 🔥🔥.
Keep it up, NesoAcademy👍👍

[rockybrother]

Exactly same question arise in my mind 13:28 . Even I feel that you are going wrong 😅 but now everything is clear.

[Umar-bnvk]

You heard the question of my heart...lots of love ❤️

[mobel]

The above PDA works fine only with w = (a+b)* not with (a+b)^+

[Apoorvpandey]

It should accept "abab" as well?