Программа для машины Тьюринга, способная распознавать язык 1^n0^n, где n>0

Формальное определение машины Тьюринга (TM)

Машина Тьюринга — это набор из 7 (Q, Σ, Γ, δ, q0, qaccept, qreject), где Q, Σ, Γ — все конечные множества и

1. Q — множество состояний,

2. Σ — входной алфавит, не содержащий пустого символа B,

3. Γ — ленточный алфавит, где B ∈ Γ и Σ ⊆ Γ, 4. δ: Q × Γ→Q × Γ × {L, R} — функция перехода,

5. q0 ∈ Q — начальное состояние,

6. qaccept ∈ Q — состояние принятия, и
7. qreject ∈ Q — состояние отказа, где qreject != qaccept.

1. Q= {q0, q1, q2, q3, q4}
2. Σ= {0, 1}
3. Γ= {0, 1, X, Y, B}
4. qs= q0
5. qпринять = {q4}
6. qотклонить = {Ø}
7. δ задается следующей таблицей переходов

printf("Введите строку: ");

иначе если(inpstr[head]=='Y')

иначе если(inpstr[head]=='Y')

иначе если (inpstr[head]==’0’)

иначе если(inpstr[head]=='Y')

иначе если(inpstr[head]=='X')

иначе если (inpstr[head]==BlankSpace)

Первоначально опубликовано на bloggernf.blogspot.com.