Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Чтобы получить «автоматную характеристику» мета-линейных языков, нам придется ввести два новых класса МП-машин.
Будем называть МП-машину чисто стирающей, если множество ее состояний можно разбить на четыре попарно непересекающиеся подмножества: Qi («состояния прямого хода»), фг («состояния обратного $ода»),
I
ЛИНЕЙНЫЕ И МЁТАЛИНЕЙНЫЕ языки
171
Q3 («состояния перехода к прямому ходу») и Q4 («состояния перехода к обратному ходу») так, что: а) ни в одной инструкции не встречаются одновременно состояния из Qi и из Q2; б) если q е Qs, то q может встречаться только в инструкциях вида AQq"~>q и q -*? A0q', где q" «= Q2 U Q4, q' <= Qj U Q4 и A0 — выделенный рабочий символ, один и тот же во всех инструкциях этого вида и не входящий ни в какие другие инструкции; в) если q е Q4, то q может встречаться только в инструкциях вида q' -> Aq и Bq -> q", где q' <^QX U Q3, q"^.Q2[}Q3, г) начальное состояние и все заключительные состояния принадлежат Q3.
Ясно, что чисто стирающая МП-машина может переходить от уничтожения рабочих ячеек к их созданию, лишь уничтожив всю рабочую ленту (поскольку в крайней слева рабочей ячейке всегда пишется символ Л0, который нигде больше не может быть записан).
Будем говорить далее, что МП-машина М имеет ограниченное число поворотов, если существует такое число k, что в любом полном вычислении этой машины направление движения рабочей головки изменяется не более k раз. Наименьшее из таких чисел k будем обозначать П(М); если П(М)= I, будем называть М машиной с I поворотами.
Таким образом, однодорожечная МП-машина — это чисто стирающая машина с одним поворотом. Впрочем, для любой МП-машины с одним поворотом очевидным образом строится эквивалентная ей однодорожечная.
В отличие от предыдущих классов МП-машин, машины с ограниченным числом поворотов определяются не в терминах программ, а в терминах вычислений. Однако ниже (замечание к теореме 5.11) будет показано, что по программе произвольной МП-машины М можно распознать, имеет ли она ограниченное число поворотов, и если да, найти П(М).
Теперь может быть сформулирована
Теорема 5.9. а) Для любой металинейной ОЪ-грам-матики можно построить эквивалентную ей чисто стирающую МП-машину с ограниченным числом поворотов. б) Для любой чисто стирающей МП-машины с ограниченным числом поворотов можно построить эквивалентную ей металинейную ОЪ-грамматику.
172 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. в
Для доказательства этой теоремы нам понадобится следующая очевидная лемма.
Лемма 5.1. Пусть М и М' — МП-машины, и пусть Ми М2, М* — их параллельная и последовательная композиции и итерация М соответственно. Тогда: а) если М и М' — чисто стирающие машины, то таковы же Ми Мч и М*\ б) если М и М' имеют ограниченное число поворотов, то это верно и для М\ и М2, причем
П (Mi) < шах (П (М), П (М')), П (М2) < П (М) + П (АГ).
Заметим теперь, что для машин с одним поворотом утверждение пункта а) теоремы 5.9 справедливо в силу теоремы 5.8; поэтому для общего случая оно следует из леммы 5.1.
Доказательство пункта б) нам будет удобно ненадолго отложить.
С помощью теоремы 5.9 легко указать примеры нелинейных металинейных языков (упражнение 5.26).
Металинейные языки допускают естественное обобщение в двух направлениях. С одной стороны, можно рассматривать языки, допускаемые машинами с ограниченным числом поворотов, отказавшись от требования чистоты стирания, с другой — допускаемые чисто стирающими машинами без ограничения на число поворотов. Первой возможности будет посвящен следующий параграф, а сейчас мы займемся второй.
Теорема 5.10. а) Для любого бескоэффициент-ного регулярного выражения 51 (|ь ..., gn+i) ат переменных gi, ..., In, In+i и любых п линейных ОБ -грамматик Ti, ... ,ГП можно построить чисто стирающую М.П-машину, допускающую язык 9l(L(ri),..., L(r„),A). б) Для любой чисто стирающей М.П-машины М можно построить бескоэффициентное регулярное выражение (|i, ..., In, En+i) и линейные ОЪ-грамматики
Гь Г„ такие, что «С(Z.(Гх),..., 1(Г„), А) = L(M).
Доказательство, а) Следует из теоремы 5.8 и леммы 5.1. б) Пусть М — чисто стирающая МП-машина, и пусть qa, <7р — два произвольных состояния перехода к прямому ходу. Выбросим из программы М все инструкции, содержащие состояния .перехода к прямому ходу, кроме тех, которые содержат qa в левой части или qр в правой, и при этом заменим q$ его «двойником» —
§ s.3]
ЛИНЕИНЫЕ И МЕТАЛИНЕЙНЫЕ ЯЗЫКИ
173
новым состоянием q^ («двойники» различных состояний различны). Начальным состоянием новой машины, которую будем обозначать Ма$, объявим qa, единственным заключительным состоянием — q^. Afag является, очевидно, машиной с одним поворотом*), и для нее по теореме 5.8 можно построить эквивалентную линейную ОБ-грамматику Гар. Сопоставим каждой машине М новый символ аар и рассмотрим диаграмму D, строящуюся так: узлами ее служат состояния перехода к прямому ходу машины М — пусть это q\, ..., qp\ начальными и заключительными узлами будут начальное и заключительные состояния М соответственно; из qa в q$ идет точно одна дуга, и эта дуга помечена символом aag. Если L0 — множество всевозможных цепочек, производимых полными путями диаграммы, то, очевидно,
