in Theory of Computation retagged by
5,519 views
17 votes
17 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.

  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\}$ 
in Theory of Computation retagged by
5.5k views

2 Comments

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

0
0

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

2 Answers

27 votes
27 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)
selected by
by

4 Comments

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.
0
0
Here then how empty string is accepted?
0
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 nonempty even palindromes over the set

1
1
12 votes
12 votes


This is NPDA

4 Comments

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

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

0
0

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

1
1

Related questions