Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
38
ОСНОВНЫЕ понятия
[ГЛ. I
применять и раньше — это ничего не изменит). Так получается любая цепочка вида (/г I)2, и ясно, что
только такие цепочки в словаре {|} выводимы из / по правилам I—X. Цепочка ] = 12 получается по правилу XI.
Дальнейшие примеры «абстрактных» грамматик см. в упражнениях 1.14 и 1.15 (см. также упражнение 3.6).
Пример 14. Пусть Г= (V, W, ПРЕДЛ, R), где
1) V состоит из словоформ русского языка;
2) W состоит из символов ПРЕДЛ, Stxyz, Stxyz, Axyz, Vjy, Loc*> где t = одуш, неодуш; x = муж, жен, ср; у — ед, мн; z = им, род, дат, вин, твор, предл; i = 1, 2,
3, 4, 5; Ч*1 есть произвольная подпоследовательность последовательности 12345 (возможно, пустая).
Содержательная интерпретация вспомогательных символов: ПРЕДЛ — «предложение»; StXyz — «группа существительного, одушевленного или неодушевленного в зависимости от t, рода х в числе у и падеже г»; StXyt — «существительное» (смысл индексов тот же); АХуг — «прилагательное в роде х, числе у и падеже z»\ VХу — «(непереходный) глагол в изъявительном наклонении, прошедшем времени, роде х и числе у вместе с обстоятельствами тех типов (см. ниже), номера которых входят в \F»; Loc*— «обстоятельства различных типов, характеризующие движение», а именно Loci — «путь» (по дороге, по воздуху), L0C2 — «отправной пункт» (из деревни, от реки), Loc3 — «пункт назначения» (в лес, на концерт), L0C4—«придорожные предметы» (мимо деревни, вдоль опушки), L0C5 — «способ передвижения» (пешком, в карете).
3) R состоит из следующих правил (всюду, где не оговорено противное, индексы принимают все допустимые значения):
I. ПРЕДЛ -+§txBmy]$*
II. ПРЕДЛ -> Vlxyi5Stxy Им
• Ilia. V^->-V^_fLoCi (здесь предполагается, что 'F содержит г; Т — / означает последовательность, получаемую из Ч*1 выбрасыванием г)
Шб. VXyStxy нм Vху Stxy им
IV. Vly->VXy
Машины Тьюринга
3§
Va. §txyz-> AxyzStxyг, если либо г ф вин, либо у = ед и х Ф муж
если л:=муж или у = мн
VI. Stxyz-* Sfxyz
VHa. 5одуш муж уг -> ямщик уг, па-р6НЬрг> ...
5неодуш ср yz ^ ПОЛву2t КО-
ЛвСОуг, ...
VII6. Ахуг —>молодойхдг, сверхскоростнойхуг, .. *
VIIb. VХу~>ехалху, летелху, ...
Vllr. LoCj У ПО SfXy дат»
LoC2~*U3 Sfxy род, ОТ SfXy род,
L0C3—>в Sfxy Внн> Wfl 5(ХуВНН,
К Sfxy дат»
LoC4 ^ MU-MO S^xy род» вОоЛЬ SfXy род,
L ос5-> пешком, верхом,
НС1 SfXy предл» ® ^ixy предл*
Читатель легко проверит, что язык L(T) содержит такие, например, цепочки, как Ехал ямщик мимо деревни, Ехала деревня мимо ямщика, Молодая очаровательная ведьма летела на межобластной шабаш на сверхскоростном турбореактивном помеле.
§ 1.4. Машины Тьюринга
Машины Тьюринга и различные их разновидности играют в теории грамматик чрезвычайно важную роль. С одной стороны, выявление связей и параллелей между теорией машин и теорией грамматик позволяет лучше понять главные идеи последней; с другой — при изучении грамматик глашины Тьюринга нередко оказываются удобным техническим средством.
(Здесь ямщикух и т. п. — сокращенная запись; например,
ЯМЩиКроп. мн.
означает
ямщиков.)
Vб . 50душ ху вин —> АХу род^одуш ху ВИН VВ. 5Heonvul vo вин ^ Ахи «M^HeoHvui хи вин
40
ОСНОВНЫЕ понятия
[ГЛ. I
Концепция машины Тьюринга, которой мы будем пользоваться, отличается от обычной, излагаемой в руководствах по теории алгоритмов (см., например, [КДеепе 1952]). Поскольку наше изложение рассчитано на читателя, знакомого с основами теории алгоритмов, мы не будем в основном тексте касаться вопроса о взаимоотношении нашей концепции с обычной и отнесем это в упражнения. По той же причине мы , не разбираем примеров и проводим рассуждения о машинах Тьюринга по большей части «на пальцах», на уровне объяснения руководящих идей (но достаточно подробно, чтобы знакомый с соответствующей техникой читатель мог восстановить все формальные детали; тем, кто найдет свой уровень владения этой техникой, недостаточным, полезно выполнить упражнения 1.16—1.19). Само определение машины также не будет,до конца формализованным; в нем будут' "фигурировать такие наглядные образы, как «лента», «ячейка, обозреваемая головкой» и т. п.; впрочем, в этом мы следуем традиции.
Обычная «классическая» машина Тьюринга представляет собой устройство для реализации алгоритмов. Работа алгоритма есть детерминированный процесс: каждый следующий его шаг жестко определяется предыдущим, и ход всего процесса полностью предопределен исходными данными. Для достижения такой детерминированности на машину Тьюринга в ее классическом виде накладывается требование ни в какой момент не допускать возможности выполнения двух разных команд. Нам, однако, понадобятся и такие машины Тьюринга, которые реализуют не алгоритмы, а исчисления, сходные с грамматиками, — «недетерминированные машины Тьюринга»; формально они будут отличаться от обычных только отсутствием упомянутого только что требования. Впрочем, термин «недетерминированная машина Тьюринга» неудобен: детерминированная машина оказывается частным случаем недетерминированной. Поэтому мы будем называть недетерминированные в указанном только что смысле машины просто «машинами Тьюринга», а «классические» — «детерминированными машинами Тьюринга».
