Examples of Decidable problem:

E is recursive:

Theorem:

 E is recursive.

Proof:

We can construct a regular expression for E according to the  definition of the encoding function as shown below:

R = S 1 (M #)+

S = 0

M = Q , A , Q , A , D Q = 0+

A = 0+

D = 0 + 00 + 000

Then, E is regular, and thus recursive.

SA is recursively enumerable

• Construct a TM S accepting SA
• If w is not e(T) for some TM T, S rejects w.
• If w is e(T) for some TM T, S accepts e(T) iff T accepts e(T).

• L(S) = {w| w=e(T) for some TM T accepting e(T) = SA.
• Then, SA is recursively enumerable.

SA is not recursive

• NSA = E - SA
• NSA is not recursively enumerable, and therefore not recursive.
• But E is recursive.
• From closure property, if L1 and L2 are recursive, then L1 - L2 is recursive.
• By using its contrapositive, if L1 - L2 is not recursive, then L1 or L2 are not recursive.
• As NSA is not recursive and E is recursive, then SA is not recursive.

Co-R.E.

Definition

• A language L is co-R.E. if its complement L' is R.E.
• It does not mean L is not R.E.

Examples:

• SA is R.E. S'A=E'∪NSA is not R.E.

-    S'A is co-R.E., but not R.E.

• NSA is not R.E. N'SA= E'∪SA is R.E.

-    NSA is co-R.E., but not R.E.

• E is recursive, R.E., and co-R.E.

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