Decidable and Undecidable problems:
Accepting:
Definition
- Let T = (Q, Σ, Γ, δ, s) be a TM.
- T accepts the string w in Σ * if (s, Δw) |-T* (h, Δ1) .
- T accepts the language LΣ⊆* if, for any string w in L, T accepts w.
Characteristic function
- For any language LΣ⊆*, the characteristic function of L is function ΧL(x) so that
|
-
|
ΧL(x) = 1
|
if x∈L
|
|
-
|
ΧL(x) = 0
|
otherwise
|
Let L = {w∈{0,1}* | n1(ω) <n0(ω) <2n1(ω) }, where nx(ω) is the number of x's in ω}.
|
-
|
cL(ω) = 1
|
if n1(ω) <n0(ω) <2n1(ω)
|
|
-
|
cL(ω) = 0
|
otherwise
|
Deciding: Definition
- Let T = (Q, Σ, Γ, δ, s) be a TM.
- T decides a language LΣ⊆* if T calculates the characteristic function of L.
- T decides a language LΣ⊆* if
- for any string ω in L, T stops on w with output 1,
- for any string ω in'L, T halts on w with output
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 Decidability in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.