4,456 views

Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the language which is the set of all nonempty even palindromes over the set $\left\{a,b\right\}$. Below is an incomplete specification of the transitions $\delta$. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.

1. $\delta(q_1,a,\bot) = \left\{(q_1, \bot a)\right\}$
2. $\delta(q_1,b,\bot) = \left\{(q_1, \bot b)\right\}$
3. $\delta(q_1,a,a) = \left\{(q_1, aa)\right\}$
4. $\delta(q_1,b,a) = \left\{(q_1, ab)\right\}$
5. $\delta(q_1,a,b) = \left\{(q_1, ba)\right\}$
6. $\delta(q_1,b,b) = \left\{(q_1, bb)\right\}$
7. $\delta(q_1,a,a) = \left\{(\dots, \dots)\right\}$
8. $\delta(q_1,b,b) = \left\{(\dots, \dots)\right\}$
9. $\delta(q_2,a,a) = \left\{(q_2, \epsilon)\right\}$
10. $\delta(q_2,b,b) = \left\{(q_2, \epsilon)\right\}$
11. $\delta(q_2,\epsilon,\bot) = \left\{(q_2, \epsilon)\right\}$

Here we dont have any FS,so we must accept using empty stack. So this is the NPDA

@Arjun @othergenerouspeople

Q=({q1,q2},{a,b},{a,b,⊥},δ,⊥,ϕ)

Can somebody please expand the info obtained by just  this notation for me ??? How do you read it .?

$\delta(q_1,a,b) = \left\{(q_2, ba)\right\}$ means from state $q_1$ on input $a$ with stack top being $b$, the PDA moves to state $q_2$ and pushes $a$ on top of stack.

So, here the missing transitions are at the middle of the input string:

$\delta(q_1,a,a) = \left\{(q_2, \epsilon)\right\}$
$\delta(q_1,b,b) = \left\{(q_2, \epsilon)\right\}$

Once middle is reached, now we should start popping. And so, we must go to state $q_2$ as well as pop the previous character on the stack. (The character before and after the middle must be same as the string is even length palindrome)

(This is a non-deterministic PDA)
by

No, Here at the middle (q2,aa) means one extra a is pushed on stack. So, the accepted string will not be a palindrome anymore.

(q2,a) is needed for odd length palindrome. Then it accepts odd length palindromes like abaaaba, but still not the ones like abababa.
Hello sir How can we find the middle for given string ? here they mentioned Even length palindrome according to that we find middle Is this correct ?
We are not finding the middle- and that is why it is a non-deterministic PDA. After each character we guess if it is the middle or not.
Sir , still the string ababab is not accepted by this PDA as there is no scenario when input is a and TOS is a , or when input is b and TOS is b and we could reach the final state .
ababab is not palindrome rt?
So sorry ,mind has stopped working these days .
:) just keep calm. Remaining days just do not over stress :)

δ(q1,a,a)={(q2,ϵ)}
δ(q1,b,b)={(q2,ϵ)}

It's because, it is mentioned in the question that it accepts even length palindrome.

Suppose if the PDA was to accept odd length palindromes then missing transitions will be:

δ(q1,a,a)={(q2,a)}
δ(q1,b,b)={(q2,b)}

yes manu thakur i think u r right
even palindrome means $ww^{r}$

@Manu Thakur sir what is the meaning of these lines "pushdown automaton accepting by empty stack for the language"?

It means that there is no final state. Whenever the input string has exhausted and the stack top is Z (or \$ or whatever the defined stack symbol is) then the string is accepted, otherwise not. So basically instead of having a separate final state to accept the language, we can just define a transition to check if the input is epsilon and the stack symbol is Z to accept the language.

Here, the above transition is transition 11 – δ(q2,ϵ,⊥)={(q2,ϵ)}. Instead of having a separate final state q3, we are accepting the string in q2 itself through empty stack.
Here then how empty string is accepted?

@Amlan Kumar Majumdar It is given non-empty string.

be a pushdown automaton accepting by empty stack for the language which is the set of all nonempty even palindromes over the set

This is NPDA

@akash.dinkar12 Yes, made sense. Bhai, may you please explain the 11th transition function?

### I mean, (ϵ,⊥/⊥) this transition in your PDA.

It means you have scanned the entire string and now only the initial stack symbol is left. So our string is a palindrome now we will leave the initial stack symbol as it is and will go to the final state.

@raja11sep this is completely wrong bcz when we accept string by emptying stack ,then there will be no final state.

•  is a finite set of states
•  is a finite set which is called the input alphabet
•  is a finite set which is called the stack alphabet
•  is a finite subset of , the transition relation
•  is the start state
•  is the initial stack symbol
•  is the set of accepting states

,

this the description of pda with emptying statck.So you can easily see no final state