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

Dark Mode

4,337 views

16 votes

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.

- $\delta(q_1,a,\bot) = \left\{(q_1, \bot a)\right\}$
- $\delta(q_1,b,\bot) = \left\{(q_1, \bot b)\right\}$
- $\delta(q_1,a,a) = \left\{(q_1, aa)\right\}$
- $\delta(q_1,b,a) = \left\{(q_1, ab)\right\}$
- $\delta(q_1,a,b) = \left\{(q_1, ba)\right\}$
- $\delta(q_1,b,b) = \left\{(q_1, bb)\right\}$
- $\delta(q_1,a,a) = \left\{(\dots, \dots)\right\}$
- $\delta(q_1,b,b) = \left\{(\dots, \dots)\right\}$
- $\delta(q_2,a,a) = \left\{(q_2, \epsilon)\right\}$
- $\delta(q_2,b,b) = \left\{(q_2, \epsilon)\right\}$
- $\delta(q_2,\epsilon,\bot) = \left\{(q_2, \epsilon)\right\}$

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

1

26 votes

Best answer

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

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)

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

0

@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

nonemptyeven palindromes over the set

0

12 votes

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

0

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

0

@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

0