search
Log In
1 vote
417 views
L = { ${\epsilon }$ } is a

a) regular

b) CFL

c) CSL

d) recursive language
in Theory of Computation
edited by
417 views

1 Answer

2 votes
 
Best answer

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


selected by
1
Then it is also recursive. rt?
But epsilon is not accepted by a TM. Why?
0
does it imply that TM or LBA can be built to accept  L = {ϵ}
0

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

Related questions

0 votes
2 answers
1
2.2k views
Context sensitive grammar can be recognised by A)finite state automata B)2 way linear bounded automata C)Pushdown automata D)None of these
asked Jun 24, 2016 in Compiler Design vivekpinto07 2.2k views
0 votes
2 answers
2
126 views
it is given that in csg if @-># then length of @ should be less or equal to # then how aaB->c is a csg???
asked Apr 7, 2018 in Theory of Computation Ravi prakash pandey 126 views
0 votes
0 answers
3
127 views
How can L(G) be regular? If we derive bSb --> bAcAb, now we have Ab-->b but we do not have the production bA since G is all production except last. So there is no production for A or bA. How can we go further?
asked Jan 12, 2017 in Theory of Computation Purple 127 views
3 votes
2 answers
4
...