2 votes 2 votes Not able to understand whether it is CFL or not due to the condition 'm>=481'. Theory of Computation theory-of-computation context-free-language pushdown-automata dcfl + – Ashish Sharma 3 asked Dec 22, 2017 Ashish Sharma 3 1.6k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Anu007 commented Dec 22, 2017 reply Follow Share push for a and pop for b . try this for any string 0 votes 0 votes srestha commented Dec 22, 2017 reply Follow Share here 2 comparison. Can it be done in 1 stack? 0 votes 0 votes reboot commented Dec 27, 2020 reply Follow Share @srestha ma’am isn’t it regular too? Like we can have a DFA for 581 m. And then For n=1, we will have 1 path, for n=2 we will have another path and so on till n=581. And then for n=582 we’ll have dead state. hence regular. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes L= {a^n b^m |n<= m & 481<=m} lets take small version of this language L= {a^n b^m |n<= m & 1<=m} then strings in above lang are {b,ab,abb,abbbbb, abbbbb.......} DPDA for lang is given below. Akash Mittal answered Dec 22, 2017 Akash Mittal comment Share Follow See all 2 Comments See all 2 2 Comments reply juuniversity commented Jul 4, 2021 reply Follow Share It's not Dpda... it's pda.. please correct this 0 votes 0 votes juuniversity commented Jul 5, 2021 reply Follow Share On q1 (second state) q1(b,zo/zo) and q1(€,zo/zo) make violation of Dpda definition...which makes Npda... please read Dpda definition.. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Please let me know this DPDA is correct for the above language or not. I will say this language is DCFL. Ashish Sharma 3 answered Dec 22, 2017 Ashish Sharma 3 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes since a value of m is defined on a certain number which is finite and the comparison of n and m is possible using the stack. So it is CNF Raj Kumar 7 answered Dec 23, 2017 Raj Kumar 7 comment Share Follow See all 0 reply Please log in or register to add a comment.