Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 25

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 101 >> Следующая


.. Второй случай соответствует действию, состоящему в передвижении ленты на одну ячейку влево и переходе из состояния qt в состояние qu

... Третий случай соответствует передвижению ленты на одну ячейку вправо и переходу из состояния qt в состояние qi. Из определения (5) непосредственно следует, что . если а -* ? и а—*у, то ? = Y2);

.. если Z и Z' — две машины Тьюринга, такие, что всякая команда машины Z есть команда машины Z' (в этом случае пишут Zc=Z'), то из а—»? относительно Z следует а—»? относительно Z'.

Вычисления. Конфигурация а называется заключительной относительно машины Z, если не существует конфигурации ? этой машины, такой, что а—>-?.

') Чтобы это утверждение имело смысл, конфигурации, определенные абстрактным образом как цепочки некоторого специального вида, должны быть интерпретированы в терминах «частей» машины.

Здесь имеется в виду следующая интерпретация. Прежде всего предполагается, что в каждый момент лишь конечное число ячеек непусто (иначе говоря, занято символами, отличными от В). Тогда цепочка, получаемая из конфигурации вычеркиванием символа qi, интерпретируется как последовательность символов, записанных подряд, слева направо, в некотором куске ленты, содержащем все непустые (в данный момент) ячейки; qi означает состояние машины в данный момент; вхождение символа, перед которым стоит qi, — то, которое в данный момент читается. — Прим. ред.

2) Здесь используется детерминированность машины, т. е. требование различия начальных пар символов в различных командах. — Прим. ред. Гл. IV. Алгоритмы. Машины Тьюринга

73

Назовем вычислением машины Тьюринга Z последовательность конфигураций

«1» <*2.....ар>

таких, что a.{-*<Xi+i (l-*Ci<p) и ар— заключительная конфигурация (относительно Z). Будем писать

Cip = PeaZ(O1),

что означает: «аР есть результат переработки ai машиной Z».

Начальная конфигурация. Условимся считать, что в общем случае машина перерабатывает слово, записанное в алфавите {Si}; при этом S0 обозначает пустой символ и исходное слово окружено пустыми символами с обеих сторон. Машина располагает таким количеством пустых ячеек, какое необходимо ей для вычислений. Одно из состояний машины принимается за начальное-, машина начинает работу, находясь в этом состоянии, причем головка установлена перед самым левым (непустым) символом, записанным на ленте.

4.2.3. Примеры машин Тьюринга

Пример I. Пусть машина Z имеет алфавит 51 = {So, Si, S2} и состояния <7ь <72, <7з; состояние <7! является начальным. Поведение

машины описывается следующими командами:
<7! S0 Л <7i (1)
<7i S2 Л <7i (2)
<7i Si Л <72 (3)
<72 Si П <7з (4)
<72 S0 Л 9, (б)
<72 S2 Л <7i (6)
<7з S2 <7з (7)

Пояснения, а) Если машина находится в начальном состоянии <7j и читает символ S0 или S2, то она сдвигает ленту на одну ячейку влево, оставаясь в состоянии <71; теперь головка обозревает символ, стоящий в ячейке непосредственно справа от S0 или S2 (команды (1) и (2)).

б) Если машина находится в состоянии <7! и читает символ Sb ю она сдвигает ленту на одну ячейку влево и в результате начинает обозревать символ, соседний справа к Si. При этом она «запоминает» тот факт, что видела Si: состояние q2 можно интерпретировать как информацию о том, что был прочитан символ Si (команда (3)).

в) Если, все еще «помня об Si», машина видит S0 или S2, она забывает, что видела Sj (возврат в состояние <71), и переходит к 74

Часть /. Предварительные сведения из логики и алгебры

обозреванию символа, стоящего непосредственно справа от S0 или S2 (команды (5) и (6)).

г) Если, напротив, находясь в состоянии q2 («помня об Si»), машина снова видит Si, она возвращается к предыдущему символу (это как раз тот Si, который привел ее в состояние q2) и переходит в состояние q3 (команда (4)). Затем она заменяет первый из этих двух соседних символов Si на S2 и переходит в состояние q3 (команда (7)). Теперь машина оказывается в ситуации ^S2, для которой нет подходящей команды; поэтому она останавливается.

д) Таким образом, единственным фактором, влекущим остановку машины, является наличие двух последовательно написанных Si. Если в процессе чтения входного слова машина не встретит двух рядом стоящих Si, то она дойдет до конца слова, перейдет на пустые ячейки справа от него и будет работать вечно (команда (1)).

Зададим машине Z, находящейся в состоянии qu слово

SjSQS2S JSJSQSJ •

В результате получится последовательность конфигураций:

S1 S0 S2 S1 S1 S0 S1 (1)
Si S0 S2 S1 Si S0 S1 (2)
Si So qi S2 S1 Si S0 S1 (3)
Si S0 S2 q 1 Sj Si S0 S1 (4)
Si SQ S2 S1 ?2 S1 S0 S1 (5)
Si S0 S2 -S1 Si S0 S1 (6)
Si S0 S2 S2 Si S0 S1 (7)

конфигурация)

Теперь предложим той же машине слово

SjS2S2.

В этом случае вычисления пойдут так:

qi Sj S2 S2 (1)

Si q2 S2 S2 (2)

S1 S2 q1 S2 (3)

Sj S2 S2 q{ S0 (4)

Sj S2 S2 S0 qі S0 (5)

Процесс продолжается вечно, т. е. результат здесь не определен.

Пример 2. Транскрибирующая машина. На ленте машины Тьюринга записано слово в алфавите ЗД {ai, ..., a„}; слева и справа его окружают пустые ячейки ф.
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed