# The following machine is designed with PDA acceptence by final state to accept odd length palindromes

1 vote
822 views

my question is as it is odd length palindrome , so  it can be ababa , right ?

Now , in the given diagram , they have not mentioned the scenario :

1)  when a is the stack top element and input symbol is b  ( b , a / ? )

2)  when b is the stack top element and input symbol is a ( a, b / ? )

Now , my question is - without these two transitions can we design this pda ? ( as it is done in the given ans )

1
In the diagram $\epsilon$ is used to show that stack top does not matter for the transition.

According to me this question is unclear but if we thinks that ∊ represents that at the top of the stack there can be anything then only we can say option c is correct ..

But in gate they will not ask such  unclear and confusing question...

at state B

there should be following transitions specified..

∱(B,b,Zo)=(B,bZ0) , ∱(B,a,Zo)=(B,aZ0) , ∱(B,b,b)=(B,bb), ∱(B,b,a)=(B,ba),

∱(B,a,a)=(B,aa) , ∱(B,a,b)=(B,ab)

Hope this will clear your doubt...

At first,  the question is confusing.

The solution which says that epsilon should be treated as anything(Zo, a, b) is correct.

The PDA already is designed to accept the Odd Length Palindromes i.e., there is no other strings in the language.

The key here is to first set your mind to that it will only be given inputs of odd length palindromes.

Another confusion is if A state is having (A, a, epsilon) → (A, a.epsilon) then why do we need to put (A, epsilon, epsilon) as a transaction again. the pick here is it is given to be a PDA which is by default NON DETERMINISTIC so we could have more than one transitions.

Also consider X transition as the transition for the special element (C or X in wCw or wXw) which will be used to go to some other state and after reaching that state we could pop each a for a and each b for b.

Let me know if there is any fallacy.

## Related questions

1
3.3k views
Number of final state require to accept &Phi; in minimal finite automata. a) 1 b) 2 c) 3 d) None of the mentioned