The Gateway to Computer Science Excellence
+1 vote
L = { ${\epsilon }$ } is a

a) regular

b) CFL

c) CSL

d) recursive language
in Theory of Computation by Junior (959 points)
edited by | 330 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

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

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  ϵ 


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
104,670 users