Register

Decidabilty Question

564 views
2 2 votes

We know given a TM (M) accepts an null string ϵ is an UD problem.

Hence, L(M) will never be Recursive, but is it R.E? 

I mean, TM (M) can accept epsilon when it can go to an accept state on "B" on input tape. So, does it make it Semi-decidable and hence R.E?

Thank you!

Note/Credits: Blue line is copied from Arjun Sir's answer. Source - here

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · union findNext → · Transactions Seriali...
← Previous in category · Regular expressionNext in category → · Some Questions on De...
Position:
Show:

Related questions

2 2 votes
2 2 answers
1.5k
1.5k views
iarnav asked Oct 22, 2017
1,476 views
Some Questions on Decidabilty
1) Is it decidable whether a given Turing machine accepts any string at all? That is, is L(M) not equal to ∅? 2) Is it decidable whether a given Turing machine accepts a...
2 2 votes
1 answers 1 answer
646
646 views
aftab0711 asked Aug 27, 2024
646 views
Decidability/Undecidability Question on CGF
Which of the following language is/are Turing decidable? 1. L = { <G1, G2 | G1 & G2 are regular grammar and L(G1) ⊆ L(G2)} 2. L = { <G, R | G is a CFG & R is a regular ex...
0 0 votes
1 1 answer
611
611 views
admin asked Jan 13, 2024
611 views
TIFR CSE 2024 | Part B | Question: 5
For two languages $\text{A, B}$ over the alphabet $\Sigma$, let the perfect shuffle of $\text{A}$ and $\text{B}$ be the language\begin{Bmatrix}w=a_1 b_1 a_2 b_2 \cdots a_...