Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Перейдем теперь к характеристике ОА-языков в терминах машин Тьюринга. Рассмотрим наиболее простой из мыслимых нетривиальных частных случаев Э-маши-ны, а именно машину, ничего не делающую на рабочей ленте, иначе говоря, имеющую инструкции только вида
(i) (стр. 42). Такую Э-машину мы будем называть конечным автоматом. Можно представлять себе
160 СПЕЦИАЛЬНЫЕ классы БЕСКОНТЕКСТНЫХ ЙЗЫКОВ (гл. S
конечный автомат как Э-машину (если угодно, МП-ма-шину) без рабочей ленты; поэтому мы будем говорить о ленте и головке конечного автомата, подразумевая входную ленту и входную головку.
Конечному автомату можно сопоставить диаграмму аналогично тому, как это было сделано для ОА-грамматик. Именно; узлами диаграммы будут состоя-ния; из узла qa в узел q$ будет идти дуга, помеченная символом а, если а Ф ф, фи автомат имеет инструю-цию qaa —*? qa; узлы qa, для которых имеются инструкции вида qi ф —? qa, будут называться начальными, узлы, принадлежащие Q0, — заключительными.
Пример диаграммы конечного автомата представлен на рис. 9; начальные узлы обведены кружками, заключительный (единственный) выделен подчеркиванием.
Цепочка, производимая путем, а также цикл и полный путь определяются для диаграммы автомата точно так же, как для диаграммы грамматики. Непосредственно ясно, что цепочка х производится путем, начинающимся в qa я оканчивающимся в q$, тогда и только тогда, когда для любой цепочки z е # V* и подходящего символа ЬеУЩф}. где V— (входной) алфавит автомата, из ситуации (qa, z, xb)’ достижима ситуация (q$, zx, Ь) *). Поэтому цепочка х производится полным путем диаграммы конечного автомата М тогда и только тогда, когда X^L(M). Автомат допускает пустую цепочку тогда и только тогда, когда пересечение множеств начальных и заключительный узлов не пусто.
Рис. 9.
*) В обозначениях ситуаций опущены компоненты, относящиеся к рабочей ленте.
§ 5.1] АВТОМАТНЫЕ И ОБОБЩЕННЫЕ ДВТОМАТНЫЁ ЯЗЫКИ (61
Различие между диаграммами грамматики и автомата сводится к тому, что первая имеет единственный начальный узел, чего не требуется от второй. Поэтому для всякой ОА-грамматики можно построить эквивалентный ей конечный автомат. Однако верно и обратное, поскольку для всякого конечного автомата можно построить эквивалентный ему конечный автомат с единственным начальным узлом в диаграмме: достаточно ввести новое состояние q' и новую инструкцию^ изъять все старые инструкции вида >qa и до-
бавить всевозможные инструкции вида q'a—*qр, где а и q$ таковы, что старая программа содержала для некоторого qa инструкции ~Qa., Ча.а ~(попросту говоря, нужно добавить к диаграмме новый узел и провести из него дуги во все те узлы, в которые идут дуги из прежних начальных узлов, пометив эти дуги теми Же символами); кроме того, если хотя бы один из прежних начальных узлов заключительный, то нужно объявить заключительным и новый начальный узел. Итак, доказана
Теорема 5.2. а) Для всякой Ok-грамматики можно построить эквивалентный ей конечный автомат.
б) Для всякого конечного автомата можно построить эквивалентную ему ОА-грамматику.
Теперь естественно заняться вопросом о взаимоотношении между детерминированными и недетерминированными конечными автоматами. Ситуация здесь существенно отлична от той, которую мы наблюдали для МП-машин: имеет место
Теорема 5.3. Для всякого конечного автомата можно построить эквивалентный ему детерминированный конечный автомат.
Доказательство. Пусть М — конечный автомат с множеством состояний Q, начальным состоянием qu множеством заключительных состояний Q0 и программой Р.
Построим новый конечный автомат М! следующим образом: а) состояниями М' будут всевозможные
подмножества Q; б) начальным состоянием будет {gi}-;
в) заключительными состояниями будут те подмножества Q, которые имеют непустые пересечения с Q0; г) программа будет состоять из всевозможных инструкций вида
6 А. В. Гладкие
162 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
Qia-^Q2, где Q, = Q и Q2 = {q^\{3qacs Ql)[qaa-+qtf=P]b. Поскольку Qi и а однозначно определяют Q2, автомат М' детерминирован. Эквивалентность М' и М усматривается без труда.
§ 5.2. Операции над ОА-языками. Регулярные языки
Теорема 5.4. Класс ОА-языков эффективно замкнут относительно операций объединения, пересечения, вычитания, взятия дополнения, умножения, итерации, усеченной итерации, подстановки, левого и правого деления на цепочку.
Доказательство. Пусть Г, Гь Г2 — ОА-грам-матики и D, Dit D2— их диаграммы. Мы можем считать, что в каждой диаграмме в начальный узел не входит ни одна дуга. (Это достигается применением конструкции
теоремы 5.1 с последующим построением эквивалентной стандартной ОА-грамматики, как указано на стр. 158.) Допустим, кроме того, что множества узлов Dt и D2 не Пересекаются. Тогда диаграмма ОА-грамматики, порождающей 1(Г4) UL(r2), получается из объединения диаграмм Di и D2 отождествлением'(«склеиванием») их начальных узлов, причем заключительными узлами новой диаграммы будут все заключительные узлы Dj и D2 (рис. 10, а)). Диаграмма ОА-грамматики, порождающей А(Г1)1(Гг), получается следующим образом: берется столько разных экземпляров D (с\попарно непересекаю-щимися множествами узлов), сколько заключительных узлов имеет Du и каждый заключительный узел Dj
