1 1 vote 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 1.6k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 2 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 4 4 Comments reply thor commented Dec 2, 2016 reply Follow flag Then it is also recursive. rt? But epsilon is not accepted by a TM. Why? 1 1 replyShare Prajwal Bhat commented Dec 2, 2016 reply Follow flag TM accepts ϵ Ref: http://math.stackexchange.com/questions/668896/what-does-it-mean-for-a-turing-machine-m-to-accept-epsilon 0 0 replyShare Neal Caffery commented Dec 2, 2016 reply Follow flag does it imply that TM or LBA can be built to accept L = {ϵ} 0 0 replyShare Prajwal Bhat commented Dec 2, 2016 reply Follow flag 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 0 replyShare Please log in or register to add a comment.
