Поддержка машины Тьюринга

У меня есть язык:

(XF*X|F)*

над алфавитом:

{X,F}

Как я могу заставить/спроектировать машину Тьюринга для распознавания этого языка? Любое руководство или совет будут высоко оценены


turing-machines finite-automata
person user3706271    schedule 25.07.2014    source источник
comment
@Rhymoid: Это совсем не похоже на исследовательский вопрос для выпускников.   -  person Jörg W Mittag    schedule 25.07.2014
comment
@JörgWMittag Хороший вопрос.   -  person    schedule 25.07.2014

Ответы (1)


arrow_upward
1
arrow_downward

Это тривиально:

digraph _ {
    _ [ shape=none, label="" ]
    1 [ shape=doublecircle ]
    2 [ shape=circle ]
    _ -> 1
    1 -> 1 [ label="F" ]
    1 -> 2 [ label="X" ]
    2 -> 2 [ label="F" ]
    2 -> 1 [ label="X" ]
}
person kay    schedule 25.07.2014
comment
Это DFA, а не ТМ. TM также имеет аннотации для направления ленты. - person ; 25.07.2014
comment
@Rhymoid, да, также он всегда записывает символ во время движения (возможно, тот же самый, который он только что прочитал). Но я думаю, ОП сумеет добавить стрелки на график… - person kay; 25.07.2014
comment
Я немного пытаюсь добавить ярлыки. Есть ли хорошая отправная точка или что-то, что могло бы мне помочь. - person user3706271; 30.07.2014
comment
Условности различаются. Я знаю условность читать, писать, направление. Например. метки будут читаться как F, F,-› или X, X,-›. - person kay; 30.07.2014