1 votes 1 votes L={ wε(a+b)* | #a - #b <=10 } CFL or Reg ? Theory of Computation theory-of-computation + – VS asked Sep 5, 2017 VS 498 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes it is CFL because we have to count for a and b and at the end match against the constraint it should not exceed 10 it cannot be done with the finite automata. nikunj answered Sep 5, 2017 nikunj comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments nikunj commented Sep 6, 2017 reply Follow Share for each a we strike one b and at the end if total number of a (which is left after striking for each b) are more then 10 then leave it other wise make it to the final state 0 votes 0 votes just_bhavana commented Sep 6, 2017 reply Follow Share @VS There will be infinite strings (even the length of strings would differ) where #a - #b <=10 holds true Refer http://gateoverflow.in/135956/identify-the-language 1 votes 1 votes Arjun commented Sep 6, 2017 reply Follow Share for every a, push a symbol on stack and for every b do a pop. When stack becomes empty and a pop is required we need to push some other symbol for 'b' and then pop the same for every 'a'. Anyway, we just need a PDA for this and no one should doubt if this is not a CFL. 2 votes 2 votes Please log in or register to add a comment.