0 votes 0 votes Please can anyone explain the PDA for reverse of a string via a transition graph Theory of Computation pushdown-automata theory-of-computation + – Devshree Dubey asked Jun 28, 2018 • edited Jun 28, 2018 by Devshree Dubey Devshree Dubey 733 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply srestha commented Jun 28, 2018 reply Follow Share what is meaning of it? 0 votes 0 votes Devshree Dubey commented Jun 28, 2018 reply Follow Share @srestha,I meant consider the string 0110,this is just but a small example of the question that I've asked. So a PDA which accepts the reverse of a string. The correction in the ques needed. I'll do it. :) 0 votes 0 votes Shaik Masthan commented Jun 29, 2018 reply Follow Share did you mean L = { WWR | W=(0+1)* } this is NPDA.... that means PDA doesn't have any idea where to PUSH and where to POP. therefore it will go by two choices.. NPDA -------PUSH the SYMBOL---------- NPDA1 | POP the SYMBOL | NPDA2 if any one of them accept the string, PDA said that String is accepted 0 votes 0 votes Devshree Dubey commented Jun 29, 2018 reply Follow Share @Shaik Masthan,Thank you so much. You've got my point.This is what I wanted to know that for a given language,how you deduced it is defined for PDA,or NPDA. You have used two NPDA here brother. Can you please help with this?Not just this language or any other kind of language as wel. A tonnes Thanks o you again. :) 0 votes 0 votes Shaik Masthan commented Jun 29, 2018 reply Follow Share let take L = { WxWR | W=(0+1)* } that means you can push all the symbols into the stack until scans x after scanning x you have to pop up from stack on successful matching.. but in case of L = { WWR | W=(0+1)* } you have no idea... " You have used two NPDA here brother " i am not only used 2 NPDA's here, may NPDA1 split into NPDA11 and NPDA12 and many more, it is not restricted.. 1 votes 1 votes Devshree Dubey commented Jun 29, 2018 reply Follow Share @Shaik Mastha,Bro, According to your explanation,if there is a symbol x in the language,then upon scanning if the symbol beyond x matches then only it will be popped from PDA.Right?This condition should hold for any other language as well which is accepted by PDA. The determinism and non-determinism is based upon this symbol x in between. Isn't it?If the symbol on the left hand side matches with that on the right hand side it is a case of determinism,else non-determinism. Am I right? 0 votes 0 votes Shaik Masthan commented Jun 29, 2018 reply Follow Share @Devshree Dubey, let take w=01011 ===> wr = 11010.. L = { WWR | W=(0+1)* } ===> Language contain 0101111010 you have no idea ( about push or pop ) at 4th 1 from left ===> NPDA L = { WxWR | W=(0+1)* } ===> Language contain 01011x11010 you have clear idea ( about push or pop ) at 4th 1 from left ===> DPDA Moreover, Note that x is a symbol which is not belongs to input alphabet. at any stage you have idea about push into the stack or pop from the stack ===> Deterministic atleast one stage you have no idea about push into the stack or pop from the stack ===> Non-Deterministic 1 votes 1 votes Devshree Dubey commented Jun 29, 2018 reply Follow Share @Shaik Masthan,A big Thanks to you brother for clearing my doubt. I've now understood what you want to convey. My doubt is now solved. Thank you for sparing your time brother.:) 1 votes 1 votes Winner commented Nov 1, 2019 reply Follow Share @Shaik Masthan if x here belongs to (a+b)* then how can I draw pda for it ,can you give some idea? 0 votes 0 votes Shaik Masthan commented Nov 1, 2019 i edited by Shaik Masthan Jul 6, 2021 reply Follow Share If x is belongs to (0+1)*, then it's npda.. DFA By keeping w = epsilon, x generate universal language. 0 votes 0 votes Please log in or register to add a comment.