XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 79

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 79)

Пусть на входной ленте автомата записана некоторая цепочка х Е У'. Допустим также, что среди состояний блока управления выделено некоторое специальное состояние, называемое кача,аьееььм, а также некоторое подмножество состояний, которые называются эанлючитпельными. В начальный момент времени блок управления находится в начальном состоянии, головка обозревает первую (крайнюю левую) ячейку ленты, в которой записан первый символ входной цепочки х.

Читая цепочку х и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии д' (точнее говоря, в этом состоянии окажется блок управления). Если это состояние является заключительным, то тогда говорят, что автомат допустил цепочку х. Спрашивается: каким образом посредством грамматики можно описать множество всех цепочек в алфавите У, которые автомат допускает? Оказывается, что каждому классу грамматик соответствует свой класс автоматов, причем для каждой грамматики соответствующего класса может быть построен автомат, который допускает цепочки, порождаемые данной грамматикой, и только их.

Образно говоря, в каждом классе языков возникает пара „писатель — читатель": грамматика, как „писатель", порождает определенное множество „текстов" (цепочек в заданном алфавите), а „читатель" (автомат) проверяет „правильность" этих текстов, допуская те и только те цепочки, которая порождает еегое грамматика. В качестве „писателя" может выступать программист, пишущий тексты компьютерных программ, а в качестве „читателя" — системные программы, обеспечивающие проверку правильности написанного текста 498 х кОнечные АВтОмАты и РеГУлЯРные Языки (соответствия его грамматике того или иного языка прогржмирования). Тем самым допускающий автомат становится прообразом некоторого распознающего алгоритма, решающего проблему принадлежности в том или ином классе грамматик.

Заметим, однако, что автомат сам по себе еще не является таким алгоритмом и что оказывается, например, в классе грамматик типа О в общем случае построить алгоритм длл решения проблемы принадлежности невозможно, хотя автома ты, соответствующие грамматнкам типа О, существуют (так называемые машины Тьюринга, см. Д.7.4). Некоторые вопросы, связанные с переходом от аналвзирующей модели языка к алгоритму, который решает проблему принадлежности для грамматики, порождающей этот язык, рассмотрены в Д.8.1. Мы начинаем с простейших анализирующих моделей — конечны* аетвомптпое.

Конечные автоматы — это анализирующие модели длл регулярных языков. Конечный автомат не имеет внутренней памяти, головка движется по ленте только вправо — на одну ячейку за такт. С ленты можно только читать. Кроме того, автомат может переходить „спонтанно" иэ одного состояния в другое, не читая ленту и не продвигая головку.

Такой такт можно рассматривать как переход иэ состояния в состояние по пусшоб веночке. Его называют Л-тактом. Итак, иэ каждого состояния автомат может переходить в другое состояние, читая тот или иной символ входной цепочки, или делать переход по пустой цепочке, причем принимается по определению, что эти два типа переходов исключают друг друга.

Поведение конечного автомата определяется его системой команд, в которой каждая команда задается записью (7.4) да-~г, что означает: „иэ состояния д по символу а Е У или по пустой цепочке (тогда а = Л) можно перейти в состояние г" (возможно, что 9=г).

7.о. Ковечвые автоматы. Теорема Кшви 499 При этом по определению принимается, что переход по пустой цепочке и переход по входному символу исключают друг друга. То есть для любой пары (д, т) состояний конечного автомата имеет место следующее: если существует команда (7.4) при а = Л, то нет ни одной команды (для такой же пары состояний) при а Е 'т' и наоборот. ХонЯивурпция нонечноео автпоааатпа определяетсл квк упорядоченное пара (д, ау), где д — состояние блока управления, а — символ в обозреваемой ячейке, у — цепочка во входном алфавите, расположенная в ячейках справа от обозреввемой (цепочку ау принято называть непронитпанноб наспшю входной цепочки). При этом если обозреваемая ячейка пуста„т.е. не содержит какого-либо символа входного злфввитв, то непрочитанная часть входной цепочки считается пустой цепочкой.

Чтобы дать математическое определение конечного автомата, нужно заметить, что он, в свете только что изложенного неформааьного описания, допускает естественную интерпретацию в терминах разаееченнмя ориентпироеанных ерафов. Будем рассматривать состояния блока управления конечного автомата как вершины ориентированного графа, множество дуг которого определяется системой команд следующим образом: дуга ведет ю состояния д в состояние т (для данных состояний д и т) тогда и только тогда, когда в системе команд автомата есть команда (7.4), т.е.

возможен переход из состояния д в состояние г. Каждая дуга имеет метку, которая является либо множеством букв входного алфавита, либо пустой цепочкой. Метка дуги (д, т) есть пустая цепочка А, если из д в т можно перейти по пустой цепочке; в противном случае метка дуги (д, т) есть множество всех входных символов, по которым возможет переход ю состояния д в состояние т. Пример Т.Т. Зададим конечный автомат с входным алфавитом [а,Ь,с) и множеством состояний (до,дпдз,дз) такой 500 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ системой команд: ЧоЛ -+ Ч1 Чо" -+ Чз Ч1а -+ Чг, Ч1Ь + Ч2 Ч1а ~ Чз, ЧЗЬ-+ Ч1, ЧзЬ-+ Чг, Чзс -+ Чг, Чзс-+ Чз.

По этой системе команд построим размеченный ориентированный граф, изображенный на рис. 7.3. Среди состояний автомата выделены начальное состояние Чо и два заключительных состояния Чг и Чз. На рис. 7.4 показана последовательность конфигураций, которую проходит конечный автомат, читал Ь цепочку аЬас. Эту цепочку авто- Ь,с мат допускает, так как, читая ее, Л он переходит иэ начального состоЧа яния в одно из заключительных.

В формальной записи последовательРие. 7.3 ность конфигураций на рис. 7.4 вы- глядит так: (Чо аЬас), (Ч1 аЬас), (Чг, Ьас), (Чп ас), (Чз, с) (Чз, Л). Этой последовательности отвечает аушь в ориентированном гРафе, веДУщий из веРшины Чо в веРшинУ Чз.

Чо +А Ч1 "+ь Ч2 ~6 Ч1 +а Чз +с Чз (под каждой стрелкой подписана буква, принадлежащая метке соответствующей дуги и являющаяся очередной буквой читаемой входной цепочки). Заметим, что, например, находясь в состоянии Ч1 и обозревая второй от конца цепочки символ, т.е. символ а, автомат мог, согласно системе команд, сделать переход в состояние Чг, а не в состояние Чз, но тогда он бы „завис" 501 7.о. Ковечвые автоматы.

Теорема Клввв Рие. 7.4 в состоянии оо и не смог бы прочитать последний символ записанной на ленте цепочки, т.е. символ с, так как среди команд нет такой, которая разрешала бы переход из состояния оз куда либо по символу с. Эта ситуация демонстрирует как рзз недетерминированность конечного автомата как распознающего устройства: система команд („правила игры") позволяет автомату допустить цепочку аЬас (еигрокуе найти последовательность ходов, ведущую к „выигрышу"), но из этого вовсе не следует, что последовательность конфигураций, которую проходит автомат, читая записанную на ленте цепочку, является единственной. Автомат может „ошибиться", сделав „неправильный" ход.

Но и последовательность „правильных" ходов может быть не единственной. Например, читая последний символ цепочки, т.е. символ с, автомат мог „выбрать" переход в состояние ея, которое также является заключительным. Рассматриваемый автомат допускает не всякую цепочку в алфавите (а, Ь, с). Видно, что ни одна цепочка, которая начинается с префикса са, не будет допущена автоматом. 502 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Обозначение пустой цепочки Л, фигурирующей в виде метки дуги ориентированного графа, который представляет конечный автомат, можно интерпретировать как регулярное выражение, т.е. как регулярный язык, состоящий из одной пустой цепочки (см.

замечание 7.4). Поскольку метка дуги, являющаяся множеством букв (Ьы..., Ьтв) С У, может быть также записана в виде регулярного выражения, а именно как сумма Ь| + ... + Ь„„то метку каждой дуги можно считать регулярным выражением определенного вида или, твк как мы отождествляем регулярные языки и регулярные выражения, регулярным языком. Это позволяет нам формально определить конечный автомат как ориенптироввнкый граф, размеченный кад иолукольиом тс(У) регулярных языков.

Такое математическое определение конечного автомата весьма удобно: оно дает нам воэможность применить при изучении конечных автоматов уже изученные нами алгебраические методы анализа размеченных ориентированных графов. Итак, математическое определение конечного автомата формулируется следующим образом.

Хонечный автпоматп — это ориентированный граф, размеченный над полукольцом Я.(У) регулярных языков в алфавите У с выделенной вершиной ов, которая называется начальной, и с выделенным подмножеством вершин г', каждый элемент которого называется эаключитпельной вершиной. На функиито рвзмешки при этом накладываются следующие ограничения: метпка каждой дуги есть либо язык ~Л~, либо непустое подмножество алфввипта У. Вершины графа называют обычно в этом случае состттолнилми конечного автпомапта, начальную вершину — начальным состполнием, а заключительную вершину — эаключитпельнмм сопполнием конечного автпоматтта.

Характеристики

Список файлов книги