Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
[Fris 1965].
1.14. Построить А-грамматики, порождающие:
а) множество всевозможных цепочек в словаре V — {в], ... ..., я*}, содержащих вхождения данной цепочки л: = at ... а1 (соответственно содержащих не менее п вхождений х, начинающихся вхождением х, оканчивающихся вхождением х, не содержащих вхождений х, содержащих ровно п вхождений л.');
б) язык V* = {* | х е V+, | х | ^ «};
в) язык C'L0) где L0 — произвольный конечный язык в V\
*) В этой работе используется термин цепочка вывода.
**) См. сноску на стр. 32.
52
ОСНОВНЫЕ понятия
[ГЛ. 1
г) язык = {х ] х е V+, | х | = si + /, / = 0, 1, ...} (s, I > 1);
д) язык ... ю+, где ©j, ..., ап — произвольные непу-
стые цепочки в V.
1.15. Построить Б-грамматики, порождающие:
а) множество правильно построенных формул логики высказываний в обычной «скобочной» записи (с фиксированным набором переменных) ;
б) то же для логики предикатов;
в) то же, что а), для бесскобочной записи;
г) то же, что б), для бесскобочной записи;
д) язык {апЬт | п, т = 1, 2, ...; я < т};
е) язык {х,6х2 | хг х2 е= {а!.ак}*\ | ж, j < | х2 |};
ж) язык {aP+mbm+ncn+P | т, п, р = 1, 2, ...};
/ п..п, п„,п„ т, т. т„ ,т„ I
з) язык [а 1Ь a pb рс ld с Pd Р\р, т-,, щ==
-1,2,...};
и) «язык Дика» Dk — множество всех цепочек в алфавите
{aj, ..., ak, al...aft}, равных единице в свободной группе со сво-
бодными образующими at, ..., ak (т. е. таких, которые могут быть преобразованы в Л последовательным вычеркиванием вхождений подцепочек вида a;dj и afii (ср. ниже, § 6.5).
1.16. Для каждого из языков упражнений 1.14 и 1.15 построить допускающую его Э-машину.
1.17. Построить ДЭ-машины, распознающие следующие числовые множества (в простейшей записи):
а) множество четных чисел;
б) произвольную арифметическую прогрессию;
в) множество полных квадратов.
1.18. Построить ДЭ-машины, вычисляющие функции:
а) l(x) = xdx (d — фиксированный символ);
б) }(*) = х/хй (ха— фиксированная цепочка).
1.19. Пусть v — некоторая стандартная нумерация словаря V и Ь ф. V. Построить ДЭ-машины, вычисляющие следующие функции:
а) v (х);
б) v-1 (п);
в) v-1 (-V (х) + 1);
г) | f (z), принимающую для каждой цепочки вида xby, где х, у е V", значение v—1 (v (я) + v (у));
д) g (г), принимающую для каждой цепочки вида xby, где лjs V*, значение v_1 (v (х)• \ (у)).
1.20. Машину Тьюринга с неэластичной рабочей лентой (Н-машину) можно определить так же, как Э-машину, с той только разницей, что рабочий алфавит дополняется «пустым символом» к и инструкции видов (и) и (iii) заменяются инструкциями вида (vi) Aqa -> Bq$, где qa,q^ е Q, A, fisf U {X}; такая инструкция означает замену в обозреваемой ячейке рабочей ленты символа А на символ В (без сдвига головки) и переход из состояния 9а в состояние
УПРАЖНЕНИЯ
53
О д н о л ен т о ч н а я машина Тьюринга с неэластичной лентой (ОН-машина) отличается от Н-машины отсутствием входной ленты, входной головки, входного алфавита и инструкций типа (i).
Детерминированные Н- и ОН-машины (ДН-ма-шины, ДОН-машины) определяются очевидным образом. (Машины Тьюринга, обычно рассматриваемые в курсах теории алгоритмов, — это ДОН-машины со следующим дополнительным ограничением: каково бы ни было незаключительное состояние q, программа машины либо содержит инструкцию (типа (iv) или (v)) с левой частью q, либо для каждого А е W содержит инструкцию (типа (vi)) с левой частью Aq.)
Ситуация, вычисление и ^-вычисление для Н-машины определяются точно так же, как для Э-машины. Начальная и заключительная х-ситуация тоже определяются аналогично тому, как это делается для Э-машины, но последней компонентой вместо # будет #АЛ, где k — произвольное натуральное число, ^-вычисление и полное .«-вычисление можно определить теперь так же, как для Э-машины; [х, ^-вычислением (у е W*) естественно назвать .«-вычисление, оканчивающееся ситуацией вида (<^, #*, ф,Л, # (<fy <= Q0)
Допускание языка и вычисление функции Н-машиной определяется так же, как для Э-машины.
Для ОН-машины ситуация определяется как тройка (<?<*> х', х") (обозначения сохраняют прежний смысл); язык is W* допускается, если вычисление, начинающееся ситуацией вида (qu Л, дЛ1) и оканчивающееся ситуацией вида (qf, Л, Xй) (qf е Q0) существует тогда и только тогда, когда х ^ L; ДОН-машина вычисляет функцию g\ L -*? W* (L s W*), если вычисление, начинающееся ситуацией вида
(q\, A, xlJ) и оканчивающееся ситуацией вида (qf, А, ули)
(qt s Qo), существует тогда и только тогда, когда у — g (х).
а) Перенести на Н- и ОН-машины теорему 1.2.
б) Перенести теорему 1.3 на ДН- и ДОН-машины, а также на
ДОН-машины с указанным выше дополнительным ограничением.
в) Показать, что классы языков, допускаемых Э-, Н-, ДН-, ОН-и ДОН-машинами, а также ДОН-машинами с вышеуказанным ограничением, совпадают, причем для всякой машины каждого из перечисленных классов можно построить эквивалентную ей машину любого другого класса.
1.21. Назовем Э-машину числовой, если ее входной алфавит состоит из единственного символа |. Язык, допускаемый (функцию, вычисляемую) числовой Э(ДЭ)-машиной, назовем числовым рекурсивно перечислимым множеством (ч. р. п. м.), соответственно числовой частично рекурсивной функцией (ч. ч. р. ф.). Для произвольного алфавита V назовем язык LeF* нумерационно рекурсивно перечислимым множеством (н. р. п. м.) и функцию f: Т -*? V* (Т s У*) нумерационно частично рекурсивной функцией (н. ч. р. ф.), если существует такая стандартная нумерация v алфавита V, что для некоторого ч. р.п. м. L' имеет место L' = v(L) —соответственно для некоторой ч. ч. р. ф. f имеет место f(x) = v~l(}'(v(x))) (знак != означает совпадение областей определения и совпадение значений в каждой точке общей области определения).
