Теория алгоритмов и формальных языков. Мелихов А.Н - 28 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

2) по команде
jki
lqxq . Лента передвигается на одну ячейку влево,
состояние q
i
меняется на q
j
: RxPq
ki
=
α
, RqPx
jk
=
β
;
3) по команде
jki
rqxq . Лента передвигается на одну ячейку вправо,
состояние q
i
заменяется на q
j
: RxqPx
ljk
=
α
, RxxPq
lkj
=
β
.
Конфигурация
α
называется заключительной, если не существует
такой конфигурации
β
, что
β
α
→
. Вычислением в МТ называется
последовательность конфигураций
α
,
β
,
γ
, m, …, n, l, таких, что
β
α
→ ,
γ
β
→ ,
m→
γ
, …,
ln →
, где l - заключительная конфигурация.
2.2. Анализ и синтез машин Тьюринга
Проблема анализ МТ состоит в том, чтобы для данной МТ определить
в каждом шаге ее реакцию на заданное входное слово, т.е. в построении
вычисления в МТ. Проведем анализ на примере конкретной МТ.
Пример 2.1. Пусть МТ задана таблицей Тьбринга
:
000
lqxq ;
001
lqxq ;
020
lqxq ;
021
lqxq ;
110
lqxq ;
2212
qxxq .
211
rqxq ;
Заметим, что эту же МТ можно задать с помощью следующих таблиц
Айзермана:
Q\х х
0
х
1
х
2
Q\х х
0
х
1
х
2
Q\х х
0
х
1
х
2
δ
:
q
0
q
0
q
1
q
0
μ
:
q
0
х
0
х
1
х
2
ν
:
q
0
l l l
q
1
q
0
q
2
q
0
q
1
х
0
х
1
х
2
q
1
l r l
q
2
- q
2
- , q
2
- х
2
- , q
2
- s -
или с помощью обобщенной таблицы:
Q\х х
0
х
1
х
2
q
0
q
0
, х
0
, lq
1
, х
1
, l q
0
, х
2
, l

Страницы