1 votes 1 votes L = { ${\epsilon }$ } is a a) regular b) CFL c) CSL d) recursive language Theory of Computation theory-of-computation identify-class-language context-sensitive + – Neal Caffery asked Dec 2, 2016 edited Dec 2, 2016 by Neal Caffery Neal Caffery 1.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 2 votes 2 votes L = ϵ is nothing but Null string if we draw the DFA the first state is final It is Perfectly Regular and since it i Regular according to chomsky hierarchy it is CFL,CSL,Recursive Prajwal Bhat answered Dec 2, 2016 selected Dec 2, 2016 by focus _GATE Prajwal Bhat comment Share Follow See all 4 Comments See all 4 4 Comments reply thor commented Dec 2, 2016 reply Follow Share Then it is also recursive. rt? But epsilon is not accepted by a TM. Why? 1 votes 1 votes Prajwal Bhat commented Dec 2, 2016 reply Follow Share TM accepts ϵ Ref: http://math.stackexchange.com/questions/668896/what-does-it-mean-for-a-turing-machine-m-to-accept-epsilon 0 votes 0 votes Neal Caffery commented Dec 2, 2016 reply Follow Share does it imply that TM or LBA can be built to accept L = {ϵ} 0 votes 0 votes Prajwal Bhat commented Dec 2, 2016 reply Follow Share TM is nothing but Finite State Machine with 2 extra stack If Finite State Machine + 1 Stack =PDA Finite State Machine +2 stack =TM So it is perfectly alright to say it is regular and since we can built a DFA so obviously yes TM can be build to accept ϵ Ref: http://math.stackexchange.com/questions/668896/what-does-it-mean-for-a-turing-machine-m-to-accept-epsilon 0 votes 0 votes Please log in or register to add a comment.