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 467 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 Warlock lord commented Sep 6, 2017 reply Follow Share By any chance can this be a CSL? Because we need another tape to count the number of a's remaining at the end? 0 votes 0 votes nikunj commented Sep 6, 2017 reply Follow Share as we know if any language is CFL then by default it is CSL because CFL is subset of CSL . 1 votes 1 votes Warlock lord commented Sep 6, 2017 reply Follow Share No what I mean is can it be NOT CFL nut only CSL? Because a^n b^n c^n for example is a CSL and not a CFL because we need an extra tape to validate c^n Had it been a^n b^n c^m it would have been a CFL because we don't need to count c..we can just scan it and finish it. 0 votes 0 votes VS commented Sep 6, 2017 reply Follow Share #a - #b <=10 so can't we reason like this that it will have finite equivalence classes and hence by Myhill Nerode theorem it is regular, I know my reasoning is wrong but where it is flawed? 0 votes 0 votes 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.