0 votes 0 votes Dpda acceptance by empty stack is equivalent in power as dpda acceptance by final state? explain Theory of Computation theory-of-computation + – Nancy Pareta asked Jul 25, 2018 Nancy Pareta 1.2k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply chauhansunil20th commented Jul 25, 2018 reply Follow Share DPDA acceptance by empty stack is NOT equivalent in power as DPDA acceptance by final state, for example there is no DPDA exist for a*b* with empty stack while we can have one with final state. 1 votes 1 votes Shubham Shukla 6 commented Jul 25, 2018 i edited by Shubham Shukla 6 Jul 25, 2018 reply Follow Share no.they are not equal in power.. languages which satisfy prefix property only gets accepted by empty stack DPDA and the ones who dont cant be accepted by empty stack..(assumption you must be knowing prefix property) for example: L={a,ab} now if you ask is it possible to accept this language by empty stack DPDA, than answer would be no because it does not follow prefix property, how lets see..? for accepting any string you need to make stack empty, like you accepted a, and you will have empty stack, now if you try to accept ab than you need to make different move for a, (because you cant choose same move again as it wont be any good for us as its lead to empty stack, once reached empty stack no moves are possible) ,which will result in loosing of determinism fact of DPDA, which you cant do in DPDA so it cant accept langauges which dont follows prefix property..so its less powerful compared to acceptance by final state.. 1 votes 1 votes Nancy Pareta commented Jul 25, 2018 reply Follow Share so can i say that all regular languages are not accepted by dpda with empty stack ? 0 votes 0 votes Shubham Shukla 6 commented Jul 25, 2018 reply Follow Share you cant say all but, yes the regular languages which dont follow prefix property wont get accepted by empty stack DPDA..! 0 votes 0 votes Nancy Pareta commented Jul 25, 2018 reply Follow Share then dpda with empty stack will become less powerful than dfa. this is incorrect and 1 votes 1 votes srestha commented Jul 25, 2018 reply Follow Share regular languages which dont follow prefix property can u elaborate this line? 0 votes 0 votes Shubham Shukla 6 commented Jul 25, 2018 i edited by Shubham Shukla 6 Jul 25, 2018 reply Follow Share @nancy pareta well.saying that i think wont be correct...:( 0 votes 0 votes Shubham Shukla 6 commented Jul 25, 2018 reply Follow Share @srestha see this link https://gateoverflow.in/135555/prefix-property you will get it easily.! 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Yes, Because if for a language dpda will exist with acceptance by empty stack then for the same language we can also give dpda with acceptance by final state. Sachin1696 answered Jul 25, 2018 Sachin1696 comment Share Follow See all 4 Comments See all 4 4 Comments reply Nancy Pareta commented Jul 25, 2018 reply Follow Share Give me a dpda diagram of Regular Language { a, ab } with empty stack acceptance? and same with final state acceptance? 0 votes 0 votes Sachin1696 commented Jul 25, 2018 reply Follow Share why you are constructing PDA for Regular Language??? 0 votes 0 votes Sachin1696 commented Jul 25, 2018 reply Follow Share dpda diagram of CFL with empty stack acceptance and same with final state acceptance. 0 votes 0 votes MrPeppermint commented Jul 25, 2018 reply Follow Share https://gateoverflow.in/148101/prefix-property-and-dpda?show=148101 https://gateoverflow.in/165012/deterministic-pushdown-automata-prefix-property https://gateoverflow.in/377/gate1999-1-6 0 votes 0 votes Please log in or register to add a comment.