2 votes 2 votes Please Explain why the following is accpeted/rejected by PDA . ( Need detail explanation ) S1 = { 0n 0m 1n 0m | n,m>0 } S2 = { 0n 0m 1n 1m 0m | n,m>0 } S3 = { am 0m 1n 1n | n,m>0} S4 = { am 0n 1n 1m | n,m>0} Theory of Computation theory-of-computation pushdown-automata context-free-language + – Anjana Babu asked Nov 24, 2016 • retagged Jul 4, 2017 by Arjun Anjana Babu 1.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 9 votes 9 votes S1 = { 0n 0m 1n 0m | n,m>0 }...it can be accepted by pda...just push all(n+m) 0s first...now when 1 comes start poping...for all n 0s,n 1s will be popped...and we will be reamining with m 0s....now when another m 0s comes just start poping....can be done easily with a stack so (deterministic) pda possible S2 = { 0n 0m 1n 1m 0m | n,m>0 }...it's not possible with a pda....first push all n+m 0s...now pop n 1s..we are left with m 0s and we have to match it with m 1s followed by m 0s...if we pop it for m 1s then nothing will remain in the stack to match it with last m 0s..so pda not possible S3 = { am 0m 1n 1n | n,m>0}....it's simple..push m number of a first then pop for m 0s.. for 1, just see if at least one 1 is there...so (deterministic) pda possible S4 = { am 0n 1n 1m | n,m>0}....it's also possible.....push m number of a..then push n 0s then pop them for n 1s..now we have m number of a in our stack....pop it off for m 1s...so (deterministic) pda possible sudsho answered Nov 24, 2016 • selected Nov 25, 2016 by Arjun sudsho comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments sudsho commented Nov 25, 2016 i edited by sudsho Nov 25, 2016 reply Follow Share @shubham DCFL means deterministic..seeing a symbol u shouldnt be confused what to do where to go..like wwr is not DCFl...how after aaaooo u accepted 111??..its 1n 1n ..means12n ...for this we dont need to do anything much just push a pop them for 0 and for 12n just make a loop....this thing in itself is even regular...just a pattern matching...nothing more.. if u still have any doubt then the grammar will be like this S->AB A->aA0/a0 B->Bcc/cc 0 votes 0 votes focus _GATE commented Nov 25, 2016 reply Follow Share sudsho for s1 : {0n 0m 1n 0m } {0n+m 1n 0m }so now i can write it as 0m 0n1n 0m this can be done non deterministically but not by dpda rt?? 0 votes 0 votes sudsho commented Nov 25, 2016 reply Follow Share no we can do it deterministically....as i said just push all 0s first ...now our stack will contain (n+m) 0s...then pop for 1 and then 0...no confusion on any transition... 0 votes 0 votes Please log in or register to add a comment.
