GATE CSE 1996 | Question: 13

Question

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\}$ 

Comments

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

 

---

@paraskk {q1,q2} -> number of states, 
{a,b} -> alphabet symbols, 
{a,b,⊥} -> symbol of stack, 
δ -> transitions, 
⊥ -> sometimes this symbol is reffered as end of the string symbol in DPDA, but here it is given as stack symbol so it must be initial stack symbol, 
ϕ -> denotes final state they are none. 

 

Answer 1

$\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)

Comments

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

---

For the above language No , Deterministic Push Down Automata is possible.

Answer 2

This is NPDA

Comments

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

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

---

@ iarnav 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