retagged by
5,541 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\}$ 
retagged by

2 Answers

Best answer
27 votes
27 votes
$\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
12 votes
12 votes


This is NPDA

Related questions

39 votes
39 votes
6 answers
2
Kathleen asked Oct 9, 2014
13,623 views
An advantage of chained hash table (external hashing) over the open addressing scheme isWorst case complexity of search operations is lessSpace used is lessDeletion is ea...
6 votes
6 votes
1 answer
3
go_editor asked Feb 10, 2018
2,337 views
Consider the synchronous sequential circuit in the below figureGiven that the initial state of the circuit is $S_4,$ identify the set of states, which are not reachable.
18 votes
18 votes
2 answers
4
Kathleen asked Oct 9, 2014
6,368 views
Consider the synchronous sequential circuit in the below figureDraw a state diagram, which is implemented by the circuit. Use the following names for the states correspon...