В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 7
Текст из файла (страница 7)
Эти символы°располагаются сначала по концам входа, и их функция — предотвратитьпереход головки за пределы области, в которой расположен вход.Конфигурация M и отношение |−M , связывающее две конфигурации, есливторая может быть получена из первой применением D, определяются так же,как и для машин Тьюринга. Конфигурация M обозначается как (q , A1 , A2 , . . .. .
. , An , i), где q ∈ Q, A1 , A2 , . . . , An ∈ Γ, i — целое от 1 до n. Предположим,что (p, A, L) ∈ D(q , Ai ) и i > 1. Будем говорить, что(q , A1 , A2 . . . An , i)|−M (p, A1 , A2 . . . Ai−1 AAi+1 . . . An , i − 1).Если (p, A, R) ∈ D(q , Ai ) и i < n, то будем говорить, что(q , A1 , A2 , .
. . , An , i)|−M (p, A1 , A2 . . . Ai−1 AAi+1 . . . An , i + 1),т. е. M печатает A поверх Ai , меняет состояние на p и передвигает головкувлево или вправо, но не за пределы области, в которой символы располагались исходно. Как обычно, определим отношение |−∗M как(q , α, i)|−∗M (q , α, i);если(q1 , α1 , i1 )|−∗M (q2 , α2 , i2 )и(q2 , α2 , i2 )|− ∗ (q3 , α3 , i3 ),то(q1 , α1 , i1 )|−∗M (q3 , α3 , i3 ).c , $ } )∗Язык, допускаемый M , — это {w | w ∈ (Σ \ { °cи (q0 , °w$, 1)|−∗M (q , α, i) для некоторого q ∈ F , α ∈ Γ∗ и целого i}.Будем называть M детерминированным, если D(q , A) содержит не болееодного элемента для любых q ∈ Q, A ∈ Γ. Неизвестно, совпадают ли классымножеств, допускаемых детерминированными и недетеминированными ЛОА.Ясно, что любое множество, допускаемое недетерминированным ЛОА, допускается некоторой детерминированной МТ (машиной Тьюринга).
Однако числоячеек ленты, требуемой этой МТ, может экспоненциально зависеть от длинывхода.2.6. Связь линейно ограниченных автоматов и КЗ-языков29Класс множеств, допускаемых ЛОА, в точности совпадает с классомконтекстно-зависимых языков.Теорема 2.7. Если L — контекстно-зависимый язык, то L допускается ЛОА.Д о к а з а т е л ь с т в о . Пусть G = (VN , VT , P , S) — контекстнозависимая грамматика. Построим ЛОА M , допускающий язык L(G). Не вдаваясь в детали построения M , поскольку он довольно сложен, рассмотримсхему его работы.
В качестве ленточных символов будем рассматриватьпары (s1i , s2i ), где s1i ∈ Σ, Σ = VT ∪ {@, $}, s2i ∈ Γ, Γ = VT ∪ VN ∪ {B}.В начальной конфигурации лента содержит (@, B), (a1 , B), . . . (an , B), ($, B),где a1 , . . ., an = w — входная цепочка, n = |w|. Цепочку символов s11 , . . ., s1nбудем называть первым треком, s21 , . . ., s2n — вторым треком. Первый трекбудет содержать входную строку x с концевыми маркерами. Второй трекбудет использоваться для вычислений. На первом шаге M помещает символS в самую левую ячейку второго трека.
Затем M выполняет процедуругенерации в соответствии со следующими шагами.1. Процедура выбирает подстроку символов α из второго трека, такую, чтоα → β ∈ P.2. Процедура заменяет подстроку α на β , перемещая, если необходимо,вправо символы справа от α. Если эта операция могла бы привестик перемещению символа за правый концевой маркер, то ЛОА останавливается.3. Процедура недетерминированно выбирает, перейти на шаг 1 или завершиться.На выходе из процедуры первый трек все еще содержит строку x, а второйтрек содержит строку γ , такую, что S ⇒ ∗G γ. ЛОА сравнивает символыпервого трека с соответствующими символами второго трека. Если сравнениенеуспешно, то строки символов первого и второго треков неодинаковы и ЛОАостанавливается без допуска.
Если строки одинаковы, то ЛОА останавливается и допускает.Если x ∈ L(G), то существует некоторая последовательность шагов, на которой ЛОА строит x на втором треке и допускает вход. Аналогично, для того,чтобы ЛОА допустил x, должна существовать последовательность шагов,такая, что x может быть построен на втором треке. Таким образом, долженбыть вывод x из S в G.Отметим схожесть этих рассуждений и рассуждений в случае произвольной грамматики. Тогда промежуточные сентенциальные формы могли иметьдлину, произвольно большую по сравнению с длиной входа. Как следствие,требовалась вся мощь машин Тьюринга. В случае контекстно-зависимых30Глава 2. Языки и их представлениеграмматик промежуточные сентенциальные формы не могут быть длиннеевхода.Теорема 2.8.
Если L допускается ЛОА, то L — контекстно-зависимыйязык.Д о к а з а т е л ь с т в о . Конструкция КЗГ по ЛОА аналогична конструкции грамматики типа 0, моделирующей машину Тьюринга. Различие заключатся в том, что нетерминалы КЗГ должны указывать не только текущееи исходное содержимое ячеек ленты ЛОА, но и то, является ли ячейкасоседней справа или слева с концевым маркером.
Кроме того, состояние ЛОАдолжно комбинироваться с символом под головкой, поскольку КЗГ не можетиметь раздельные символы для концевых маркеров и состояния ЛОА, так какэти символы должны были бы быть заменены на e, когда строка превращаетсяв терминальную.1-я группа правил — моделирование начальной конфигурации вида(q0 , @w#, 1), |w| > 1:A1 → [q0 , @, a.a]A2 ;A2 → [a.a]A2 ;A2 → [a.a, #].2-я группа правил — моделирование движения на левом конце цепочки приq ∈ F:[q , @, X , a] → [@, p, X , a], если (p, @, R) ∈ D(q , @);[@, q , X , a] → [p, @, Y , a], если (p, Y , L) ∈ D(q , X);[@, q , X , a][Z , b] → [@, Y , a][p, Z , b], если (p, Y , R) ∈ D(q , X).3-я группа правил — моделирование движения в середине цепочки приq ∈ F:[q , X , a][Z , b] → [Y , a][p, Z , b], если (p, Y , R) ∈ D(q , X);[Z , b][q , X , a] → [p, Z , b][Y , a], если (p, Y , L) ∈ D(q , X).[q , X , a][Z , b, #] → [Y , a][p, Z , b, #], если (p, Y , R) ∈ D(q , X).4-я группа правил — моделирование движения на правом конце цепочкипри q ∈ F :[q , X , a, #] → [Y , a, p, #], если (p, Y , R) ∈ D(q , X);[X , a, q , #] → [p, X , a, #], если (p, #, L) ∈ D(q , #);[Z , b][q , X , a, #] → [p, Z , b][Y , a, #], если (p, Y , L) ∈ D(q , X).5-я группа правил — восстановление входного символа в состоянии q ∈ F :на левом конце цепочки[q , #, a, X] → a, [@, q , X , a] → a;в середине цепочки[q , X , a] → a;на правом конце цепочки[q , X , a, #] → a, [X , a, q , #] → a.2.6.
Связь линейно ограниченных автоматов и КЗ-языков316-я группа правил — восстановление входной цепочки слева-направо:a[x, b] → ab,a[x, b, #] → ab.7-я группа правил — восстановление входной цепочки справа-налево:[x, a]b → ab,[@, x, a]b → ab.Отдельно для односимвольных цепочек — моделирование начальной конфигурации вида (q0 , @, a, #, 1):A1 → [q0 , @, a, a, #].Если q ∈ F :[q , @, X , a, #] → [@, p, X , a, #], если (p, @, R) ∈ D(q , @);[@, q , X , a, #] → [p, @, Y , a, #], если (p, Y , L) ∈ D(q , X);[@, q , X , a, $] → [@, Y , a, p, #], если (p, Y , R) ∈ D(q , X);[@, X , a, q , #] → [@, p, X , a, #], если (p, $, L) ∈ D(q , $).Если q ∈ F :[q , @, X , a, #] → a;[@, q , X , a, #] → a;[@, X , a, q , #] → a.Теорема 2.9.
Существуют рекурсивные множества, не являющиесяконтекстно-зависимыми.Д о к а з а т е л ь с т в о . Все строки в {0, 1}∗ можно занумеровать. Пустьxi — i-е слово. Мы можем занумеровать все грамматики типа 0, терминальными символами которых являются 0 и 1. Поскольку имена переменных неважны и каждая грамматика имеет конечное их число, можно предположить,что существует счетное число переменных.Представим переменные в двоичной кодировке как 01, 011, 0111, 01111и т. д.
Предположим, что 01 всегда является стартовым символом. Крометого, в этой кодировке терминал 0 будет представляться как 00, а терминал1 как 001. Символ «→» представляется как 0011, а запятая как 00111.Любая грамматика с терминалами 0 и 1 может быть представлена строкойправил, использующей стрелку (0011) для разделения левой и правой частей,и запятой (00111) для разделения правил. Строки, представляющие символы,используемые в правилах, — это 00, 001 и 01i для i = 1, 2, . .
.. Множествоиспользуемых переменных определяется неявно правилами.Отметим, что не все строки из 0 и 1 представляют грамматики, причем не обязательно КЗГ. Однако по данной строке легко можно сказать,представляет ли она КЗГ. i-ю грамматику можно найти, генерируя двоичныестроки в описанном порядке, пока не сгенерируется i-я строка, являющаясяКЗГ. Поскольку имеется бесконечное число КЗГ, их можно занумероватьв некотором порядке G1 , G2 , . . ..32Глава 2. Языки и их представлениеОпределим L = {xi |xi ∈/ L(Gi )}. Ясно, что L рекурсивно. По строке xiлегко можно определить i и затем определить Gi . По теореме 2.6 имеется алгоритм, определяющий для xi , принадлежит ли она L(Gi ), посколькуGi — КЗГ. Таким образом, имеется алгоритм, определяющий для любой x,принадлежит ли она G.Покажем теперь, что L не генерируется никакой КЗ-грамматикой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
