ВУЗ:
Составители:
q
1
q
0
, х
0
, l q
1
, х
1
, r q
0
, х
1
, l
q
2
- q
2
, х
2
, s -
Пусть на ленте записано входное слово х
1
х
0
х
2
х
1
х
1
х
0
х
1
, машина
находится в начальном состоянии q
0
, и головка расположена против самого
левого символа входного слова. Процесс анализа записывается следующими
конфигурациями:
q
0
х
1
х
0
х
2
х
1
х
1
х
0
х
1
х
1
q
1
х
0
х
2
х
1
х
1
х
0
х
1
х
1
х
0
q
0
х
2
х
1
х
1
х
0
х
1
х
1
х
0
х
2
q
0
х
1
х
1
х
0
х
1
х
1
х
0
х
2
х
1
q
1
х
1
х
0
х
1
х
1
х
0
х
2
q
1
х
1
х
1
х
0
х
1
х
1
х
0
х
2
q
2
х
1
х
1
х
0
х
1
В последней конфигурации МТ останавливается, так как в таблице Тьюринга
не существует команды для ситуации q
2
х
2
или, что то же самое, в таблицах
Айзермана не определен переход q
2
х
2
.
Таким образом, анализируемая МТ отсчитала четвертую букву
входного слова (х
1
), заменила ее на х
2
и остановилась.
Пусть теперь исходным словом будет слово х
1
х
2
х
2
. Процесс вычисления
выглядит следующим образом:
q
0
х
1
х
2
х
2
х
1
q
1
х
2
х
2
х
1
х
2
q
0
х
2
В
х
1
х
2
х
2
q
0
В В… и так далее
Так как ********, то в соответствии с первой командой МТ будет работать
вечно и никогда не остановится.
Рассмотрим сущность проблемы синтеза МТ и идею проведения
синтеза МТ на примере так называемых числовых МТ. В таких МТ входной
алфавит состоит из двух символов: В и | (палочка).
Произвольные (целые)
числа, представленные в числовой МТ, кодируются унарным кодом
Страницы
- « первая
- ‹ предыдущая
- …
- 27
- 28
- 29
- 30
- 31
- …
- следующая ›
- последняя »
