Undecidable problems:

• FINITE

Given a TM T, is L(T) finite?

Guess FINITE is neither R.E. nor co-R.E.

• To assure L(T) is finite, we require to run T on all the possible input and count if T accepts the finite number of strings.
• To assure L(T) is infinite, we require to run T on all possible input and count if T accepts the infinite number of strings.

FINITE is not recursive FINITE is not recursive

Let FINITE={<T>| T is a TM such that L(T) is finite.} Guess FINITE is neither R.E. nor co-R.E.

Choose NSA which is not co-R.E. to show that NSA≤FINITE.

We want to find a Turing-computable function f so that <T>∈NSA « f(<T>)=M∈FINITE

<T>∈NSA -> M accepts Φ, and thus L(M) is finite.

<T>∈NSA ->M accepts Σ*, and thus L(M) is infinite.

Then, let M=f(<T>) be a TM which runs T on its input, and accepts everything if T stops.

FINITE is not recursive

Now, we will show that <T>∈NSA ↔ <M>∈FINITE

If <T>∈NSA, then T does not accept <T>. Then, M does not get to begin AccAll. Therefore, M accepts nothing and L(M) is finite.

If <T>∈NSA, then T accepts <T>. Then, M gets pass T, and accept everything. Therefore, M accepts

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 Undecidable problems in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.