Log In
1 vote

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 )

in Theory of Computation 822 views
In the diagram $\epsilon$ is used to show that stack top does not matter for the transition.

2 Answers

0 votes

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

0 votes

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

2 votes
1 answer
0 votes
0 answers
I have gone through this link already but still couldn't catch up the logic , so please clarify what is it trying to convey ?
asked Dec 14, 2015 in Theory of Computation radha gogia 252 views
1 vote
1 answer
Set of languages accepted by DPDA by empty stack contain only those DCFL's with prefix property. and DPDA with empty stack doesnt accept any regular language too becaust it doesn't satisfy prefix property. can anyone explain this with the help of PDA ? Just take example of regular ... n >= 0 } or any language which doesn't prefix property. I just want to know where it will get stuck on PDA.
asked Jul 25, 2018 in Theory of Computation daksirp 1.3k views
2 votes
2 answers
Which of the following represent the minimum no. of states in DFA which accept all string of length atmost 5 ‘a’? 6 4 5 7 Answer given in 5 , how possible ? atmost 5 a means , on seeing 6th a , we should send it to a dead state right ? so , won't it be 7 states ?
asked Jan 14, 2016 in Theory of Computation worst_engineer 190 views