0 votes 0 votes what is the PDA for {L=$a^mb^n$ |m>n} Theory of Computation pushdown-automata theory-of-computation context-free-language + – aditi19 asked Sep 2, 2018 aditi19 944 views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Shaik Masthan commented Sep 2, 2018 reply Follow Share i didn't get your question... if your question is, is it DPDA or NPDA? then it is DPDA 0 votes 0 votes aditi19 commented Sep 2, 2018 reply Follow Share I don't know whether it is deterministic or non-deterministic. I'm confused how to approach 0 votes 0 votes MiNiPanda commented Sep 2, 2018 reply Follow Share Idea is to push for all a's and pop 1 a for each b. Since m>n so the stack must have (m-n) a's left when the string has reached it's end. So on reaching the end if top of the stack is 'a' we know that the string is in the form (ambn|m>n). I have taken n=0 so m must be atleast 1. If the string contains only a's then also it is valid(transition from q0 to q2) 0 votes 0 votes aditi19 commented Sep 2, 2018 reply Follow Share i don't think it's CFG 0 votes 0 votes Shaik Masthan commented Sep 2, 2018 reply Follow Share if you have a clarity that when to push when to pop, then it is DPDA in your example, on getting a, you are pushing and on getting b, you are poping ===> it is DPDA but take L={w.wR | w=(0+1)*}, in this language, abb . bba is in language, but on encountering b you didn't know is it going to push or pop ===> NPDA 0 votes 0 votes Shaik Masthan commented Sep 2, 2018 reply Follow Share @aditi19, check this https://gateoverflow.in/222710/pda-doubt 1 votes 1 votes Mizuki commented Sep 3, 2018 reply Follow Share @Shaik Masthan Should it not be an NPDA since there are no restrictions for m and n? 0 votes 0 votes Shaik Masthan commented Sep 3, 2018 reply Follow Share @Mizuki, what did you mean? it should be DPDA. 0 votes 0 votes Mizuki commented Sep 3, 2018 reply Follow Share @Shaik Masthan I'm asking how it is a DPDA or NPDA? 0 votes 0 votes Shaik Masthan commented Sep 3, 2018 reply Follow Share refer the previous comments which are posted by me. visit that link, it is more helpful. 0 votes 0 votes Mizuki commented Sep 3, 2018 reply Follow Share Alright, thanks! 0 votes 0 votes Shaik Masthan commented Sep 3, 2018 reply Follow Share @Mizuki if you didn't get any comment, you have the right to ask. 0 votes 0 votes Chandan Kumar 5 commented Sep 28, 2018 reply Follow Share @Shaik Masthan but I think in DPDA epsilon moves are not allowed. 0 votes 0 votes Smishra95 commented Sep 28, 2018 reply Follow Share make first state lets say Q1 . then move to new Q2(mark it as final state) when you found first a with stack top Z0 . stay at Q2 till getting A (push A).Move to new state Q3 when you get first B and stay at Q3 and pop All B. Now at Q3 if you get $(string end) and stack top still pointing to A (means no. of A's-No. of B's>0) then move to State Q2 . otherwise move to a dead state . 0 votes 0 votes Shaik Masthan commented Sep 28, 2018 reply Follow Share @chandan, I too agree that statement 0 votes 0 votes aditi19 commented Sep 28, 2018 reply Follow Share https://cstheory.stackexchange.com/questions/32271/are-dpdas-without-a-epsilon-moves-as-powerful-as-dpdas-with-them https://stackoverflow.com/questions/33000800/is-a-pushdown-automaton-with-an-epsilon-transition-a-ndpa 0 votes 0 votes Raghav Khajuria commented Sep 28, 2018 reply Follow Share Clarity means deterministic bcs b is following a so no a can come after b or b can't come before a.. DPDA would be like 0 votes 0 votes juuniversity commented Jul 5, 2021 reply Follow Share On state q2, q2(b,a,€) and q2(€,a,€) make it violating Dpda definition.... your diagram makes Npda… Please draw correct diagram... 0 votes 0 votes Please log in or register to add a comment.