Машина Тьюринга

Тема в разделе "Другие задачи", создана пользователем TuMko, 10 янв 2010.

  1. TuMko

    TuMko Гость

    Задание:
    L = {a^n b^m c^n| m, n>=1 & n<=m<=2n}

    Т.е. мы должны получить вот такие слова:
    abc
    abbc
    aabbcc
    aabbbcc
    aabbbbcc

    если слово принадлежит алфавиту, то в конце выводить 1, нет - 0
    Вот мои наброски, но они не работают что-то:

    Код (Text):
    q0 a -> q1 x R
    q0 b -> q0 b R
    q0 c -> q0 c R
    q0 ? -> q9 * R
    q0 z -> q0 z R
    q0 x -> q0 x R
    q0 e -> q0 e R
    q1 a -> q1 a R
    q1 b -> q1 b R
    q1 c -> q1 c R
    q1 x -> q1 x R
    q1 z -> q1 z R
    q1 e -> q1 e R
    q1 ? -> q2 ? L
    q2 a -> q2 a L
    q2 b -> q3 e L
    q2 c -> q2 c L
    q2 x -> q2 x L
    q2 ? -> q8 ? R
    q2 z -> q2 z L
    q2 e -> q2 e L
    q3 a -> q3 a L
    q3 b -> q3 b L
    q3 c -> q3 c L
    q3 x -> q3 x L
    q3 z -> q3 z L
    q3 e -> q3 e L
    q3 ? -> q4 ? R
    q4 a -> q4 a R
    q4 b -> q4 b R
    q4 c -> q5 z R
    q4 x -> q4 x R
    q4 e -> q4 e R
    q4 z -> q4 z R
    q4 ? -> q9 * R
    q5 a -> q5 a R
    q5 b -> q5 b R
    q5 c -> q6 c R
    q5 x -> q5 x R
    q5 e -> q5 e R
    q5 z -> q5 z R
    q5 ? -> q6 ? L
    q6 a -> q7 a L
    q6 b -> q7 b L
    q6 c -> q7 c L
    q6 x -> q6 x L
    q6 e -> q6 e L
    q6 z -> q6 z L
    q6 ? -> q11 ? R
    q7 a -> q7 a L
    q7 b -> q7 b L
    q7 c -> q7 c L
    q7 x -> q7 x L
    q7 e -> q7 e L
    q7 z -> q7 z L
    q7 ? -> q0 ? R
    q8 a -> q8 a R
    q8 b -> q8 b R
    q8 c -> q8 c R
    q8 e -> q8 e R
    q8 x -> q8 x R
    q8 z -> q8 z R
    q8 ? -> q9 * R
    q9 ? -> qz 0 L
    q10 x -> q10 x R
    q10 e -> q10 e R
    q10 z -> q10 z R
    q10 ? -> qz 1 R
    q11 a -> q11 a R
    q11 b -> q11 b R
    q11 c -> q11 c R
    q11 x -> q11 x R
    q11 e -> q11 e R
    q11 z -> q11 z R
    q11 ? -> q10 * R
    вместо ? пустой символ
     
Загрузка...

Поделиться этой страницей