Машина Тьюринга:Распознавание четности — различия между версиями
Материал из CustisWiki
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
StasFomin (обсуждение | вклад) м (→Табличное представление МТ) |
||
Строка 2: | Строка 2: | ||
== Табличное представление МТ == | == Табличное представление МТ == | ||
− | + | <latex> | |
+ | \begin{tabular}{|cc|c|ccc|} | ||
+ | \hline | ||
+ | |||
+ | 2bad & * & $\Rightarrow$ & [\textcolor{red}{q}] & 0 & \\ \hline | ||
+ | 2bad & 1 & $\Rightarrow$ & 2bad & * & L \\ \hline | ||
+ | 2ok & * & $\Rightarrow$ & [\textcolor{red}{q}] & 1 & \\ \hline | ||
+ | 2ok & 1 & $\Rightarrow$ & 2ok & * & L \\ \hline | ||
+ | <\textcolor{blue}{even}> & * & $\Rightarrow$ & 2ok & * & L \\ \hline | ||
+ | <\textcolor{blue}{even}> & 1 & $\Rightarrow$ & odd & 1 & R \\ \hline | ||
+ | odd & * & $\Rightarrow$ & 2bad & * & L \\ \hline | ||
+ | odd & 1 & $\Rightarrow$ & <\textcolor{blue}{even}> & 1 & R \\ \hline | ||
+ | \end{tabular} | ||
+ | </latex> | ||
<code-python> | <code-python> | ||
# | # |
Версия 17:41, 5 марта 2007
Приведем пример машины Тьюринга, распознающую четные входные строки (пустую строку и строки состоящие из четного числа единиц).
Содержание
Табличное представление МТ
# # Распознавание четных строк (содержащих четное число "1"). # MT={ 'k':1, 'start': 'even', 'stop': 'q', 'program': { #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте)) ('even', ('*')): ('2ok', (('*','L'))), ('even', ('1')): ('odd', (('1','R'))), ('odd', ('1')): ('even', (('1','R'))), ('odd', ('*')): ('2bad', (('*','L'))), ('2ok', ('1')): ('2ok', (('*','L'))), ('2ok', ('*')): ('q', (('1',''))), ('2bad', ('1')): ('2bad', (('*','L'))), ('2bad', ('*')): ('q', (('0',''))) } }
Графовое представление МТ
Примеры выполнения МТ
Пустая строка
«111»
«1111»
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Машина Тьюринга:Распознавание четности»