4,523 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

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