Problem of accepting an empty string:

• We will prove that the problem if a TM accepts an empty string is undecidable.
• This problem is corresponding to following language.

-   Acceptε = {e(M)| M is a TM accepting ε}

• Therefore, we will prove that Accepteis not recursive.

Accept ε is not recursive.

Proof:

(Guess Accepte is in R.E., but not co-R.E.)

• Show SA ≤ Acceptε

(We want a Turing-computable f n f(<T>)=<M> such that

-   T acceptsε (T) → M accepts ε

-   T does not accept e(T) ® M does not accept ε

• Let f(T)=M is a TM that 1st writes e(T) after its input and then runs T.

• M writes e(T) after its input. If the input is  ε, T has e(T) as input.

Acceptε is not co-R.E.

Verify that T accepts e(T) « M accepts ε

M writes e(T) and lets T run. If the input of M is ε:

• when T accepts e(T), M accepts  ε.
• when T doesn't accept e(T), then M doesn't accept  ε.

Next, we show that there is a TM TF computing f. TF works as follows:

• changes the start state of T in e(T) to a new state
• add e(Write<T>), make its start state the start state of TF, and make the transition from its halt state to T's start state.

Then, SA ≤ Acceptε.

Then, Acceptε is not co-R.E, and is not recursive.

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Problem of accepting an empty string in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.