Эквивалентность состояний конечных автоматов

ЛЕКЦИЯ № 3 Эквивалентность состояний конечных автоматов Для любого конечного автомата существует бесконечное количество других конечных автоматов, которые распознают такое же множество входных последовательностей. Можно показать, что для каждого конечного автомата существует единственный конечный автомат, распознающий то же самое множество последовательностей, при этом число его состояний не больше числа состояний любого другого конечного автомата для этого множества. В данном контексте слово «единственный» понимается, как единственный с точностью до имён состояний. Этот единственный автомат называется минимальным автоматом. Минимальный автомат является результатом приведения (или редукции) более громоздких автоматов, решающих ту же задачу. Понятие эквивалентности состояний является очень важным в минимизации и приведении автоматов. Применительно к конечным автоматам, назначение которых – допускать цепочки (последовательности) эквивалентность состояний определяется так: Состояние s конечного автомата М эквивалентно состоянию t конечного автомата N тогда и только тогда, когда автомат М, начав работу в состоянии s, будет допускать в точности те же последовательности, что и автомат N, начавший работу в состоянии t. Если два состояния s и t одного автомата эквивалентны, то автомат можно упростить, заменив в таблице переходов все вхождения имён этих состояний каким-либо новым именем, а затем удалить одну из двух строк, соответствующих s и t. 1 2 3 4 5 Пример: а в 1 4 0 3 5 1 5 1 0 2 3 1 2 3 1 а 1 3 х 2 2 1 2 3 х х в х х 1 3 3 1 1 1 1 2 3 х а 1 3 х 2 в х х 1 3 Состояние 4 и 5 объединяются в одно состояние X, так как они имеют одинаковые переходы при воздействии одинаковых символов. Если два автомата имеют эквивалентные начальные состояния, то, по определению, эквивалентности состояний, оба автомата допускают или отвергают одни и те же последовательности. Таким образом, понятие эквивалентности состояний приводит к понятию эквивалентности автоматов, а именно: Автоматы М и N эквивалентны тогда, когда эквивалентны их начальные состояния. Если два состояния неэквивалентны, то любая последовательность, под действием которой одно из них переходит в допускающее состояние, а другое – в отвергающее состояние, называется последовательностью, различающей эти два состояния. Пример: а в с а в в 1 с с а 1 x y z x z x 1 y x z 1 Состояния a и x не эквивалентны, так как их различают последовательность 101. В самом деле: а с в с x y z z причём состояние с – допускающее, а состояние z – нет. Но так как a и x – начальные состояния соответствующих автоматов, то эти автоматы неэквивалентны. Проверка эквивалентности двух состояний Пусть некоторые автоматы имеют одно и то же входное множество символов. Метод поверки эквивалентности состояний основан на следующем положении: Состояния s и t эквивалентны тогда и только тогда, когда выполняются следующие два условия: (1) Условие подобия. Состояния s и t должны быть либо оба допускающими, либо оба отвергающими. (2) Условие преемственности. Для всех входных символов состояния s и t должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны. Эти два условия выполняются тогда и только тогда, когда s и t не имеют различающей последовательности. Если нарушено хотя бы одно из этих условий то существует последовательность, различающая эти два состояния. Если нарушено условие (1), то различающей последовательностью является пустая последовательность. Если нарушено условие (2), то некоторый входной символ x переводит состояние s и t в неэквивалентные состояния. Поэтому x с приписанной к нему справа последовательностью, различающей эти новые состояния, образуют последовательность, различающую s и t. Если состояния s и t различаются некоторой последовательностью, то хотя бы одно из этих условий должно быть нарушено. Если их различает пустая последовательность (нулевой длины), то не выполняется условие подобия. Если длина различающей последовательности больше 0, то её первый символ переводит s и t в пару состояний, которые неэквивалентны, так как различаются оставшейся частью последовательности, различающей s и t. Таким образом, оба условия выполняются, если два состояния эквивалентны, и что хотя бы одно из них нарушается в случае неэквивалентности состояний. Условия (1) и (2) можно использовать в общем методе проверки на эквивалентность произвольной пары состояний. Этот метод, вообще говоря, является проверкой неэквивалентности и рассматривается как метод поиска различающей последовательности. Он поясняется следующим примером. Пример 1 2 3 4 5 6 7 y 2 2 6 1 6 6 6 z 3 5 7 7 6 5 3 3 1 1 Для записи необходимых данных строятся таблицы эквивалентности состояний. Такое построение выполняется в следующем порядке. Вначале проверяются состояния 0 и 7. Таблица эквивалентности состояний для этой проверки содержит по одному столбцу для каждого символа, т.е. для y и для z. Строки будут добавляться ходе проверки. Вначале имеется одна строка, помеченная парой состояний, подвергаемых проверке, т.е. 0, 7. Нарушения условия подобия не имеет место, так как оба состояния являются отвергающими. 0, 7 Тогда надо проверить условия преемственности. Для проверки его выполнения надо проверить воздействие на эту пару состояний каждого входного символа. Состояния 0 и 7 под действием y переходят в состояния 0 и 6 соответственно. Тогда в таблицу в столбец y записываются 0 и 6. При воздействии z оба состояния переходят в y z 0, 7 0,6 3,3 состояние 3, поэтому 3 записывается в столбец z. Для нарушения условия преемственности должны быть неэквивалентными либо состояния 0 и 6, либо состояния 3 и 3. Так как состояние эквивалентно самому себе, состояние 3 и 3 автоматически эквивалентны. Для исследования неэквивалентности состояний 0 и 6 в таблицу добавляется следующая строка. y z Процесс повторяется с новой строкой: состояния 0 и 6 неэквивалентны, т.к. 0 – отвергающее состояние, а 6 – допустимое. Отсюда 0, 6 следует неэквивалентность исходных состояний 0 и 7. Таблицу эквивалентности состояний можно построить для y z 0, 7 0,6 3 построения различающей последовательности. Строка 0, 6 появилась как результат воздействия входного символа y к паре 0, 7, поэтому y является различающей последовательностью. Проверка состояний 0 и 1 состоит из следующих шагов. Эти состояния подобны, поэтому таблица эквивалентности начинается с пары 0, 1. y z Результат применения к ним входных 0, 1 0,2 3,5 символов помещается в таблицу. Теперь необходимо проверить на эквивалентность состояние 0, 2 и 3, 5. В таблицу добавляются строки для каждой из этих пар. y z 0, 1 0,2 3,5 Состояния 0, 2 – подобны, потому необходимо вычислить следующие пары состояний для 0, 2 проверки условия преемственности. Воздействия 3, 5 входных символов заносятся в таблицу. Из двух новых элементов таблицы лишь один дает новую строку, а именно – пара 3, 7. Другой элемент, пара 0, 2 уже имеется в таблице, и нет необходимости его y z повторять. Тот факт, что пара 0, 2 порождается 0, 1 0,2 3,5 алгоритмом дважды означает, что имеются две 0, 2 0,2 3,7 входные последовательности, которые ведут из 3, 5 6 5,7 исходной пары 0, 1 в пару состояний 0, 2. 3, 7 Любая из этих последовательностей с 5, 7 приписанной к ней последовательностью, различающей состояние 0 и 2, образует различающую последовательность для состояний 0 и 1. Однако, поскольку для доказательства неэквивалентности состояний 0 и 1 достаточно одной различающей их y z последовательности, достаточно одного 0, 1 0,2 3,5 вхождения пары 0, 2 в таблицу. Следовательно, 0, 2 0,2 3,7 единственной новой строкой в таблице будет 3, 5 6 5,7 строка 3, 7. Рассмотрение состояний 3 и 5 3, 7 6 3,7 показывает, что они подобны. Так как 5, 7 6 3,5 состояние 6 эквивалентно себе, то единственной новой строкой будет 5, 7. Состояния 5,7, 3,7 и 3,5 – подобны. Никакая новая пара, требующая проверки на подобие, не появилась. Таблица оказалась заполненной, так как поиск различающий последовательности окончился неудачей. Поэтому состояния 0 и 1 эквивалентны. Общая процедура может быть описана следующим образом: 1. Начать построение таблицы эквивалентности состояний с отведения столбца для каждого входного символа. Пометить первую строку парой состояний, подвергаемых проверке. 2. Выбрать в таблице эквивалентности состояний строку, ячейки которой еще не заполнены, и проверить, подобны ли состояния, которыми она помечена. Если они не подобны, то два исходных состояния неэквивалентны, и процедура заканчивается. Если они подобны, вычислить результат применения каждого входного символа к этой паре состояний, и записать полученные состояния в соответствующие ячейки рассматриваемой строки. 3. Для каждого элемента таблицы, полученного на шаге 2, существует три возможности: Если элементом таблицы является пара одинаковых состояний, то для этой пары не требуется никаких действий. Если элемент таблицы – пара состояний, которые уже использовались как метки строк, то для неё так же не требуются никаких действий. Если элемент таблицы – это пара разных состояний, которые еще не использовались как метка, то для этой пары нужно добавить новую строку. Порядок состояний в парах не важен, и пары s, t и t, s считаются одинаковыми. После того как произведены необходимые действия для каждой пары состояний в данной строке, перейти к шагу 4. 4. Если все строки таблицы эквивалентности заполнены, исходная пара состояний и все пары состояний, порожденные в ходе проверки, эквивалентны, то проверка закончена. Если таблица не заполнена, нужно обработать, по крайней мере, ещё одну строку с помощью шага 2. Так как каждая пара, появившаяся в заполненной таблице эквивалентности состояний, содержит эквивалентные состояния, этот метод проверки часто даёт больше информации, чем предполагалось в начале. В рассмотренном примере: кроме эквивалентности пары (0, 1), которая подвергалась проверке, выявлена эквивалентность пар (0, 2), (3, 5), (3, 7) и (5, 7). По свойству транзитивности из эквивалентности пар состояний 0, 2 и 0, 1 следует эквивалентность пары (1, 2). Таким образом, состояния 0,1 и 2 эквивалентны друг другу. Аналогично, эквивалентны друг другу состояния 3, 5, 7. Для упрощения автомата эквивалентные состояния объединяются в одно состояние. Состояния 0, 1, 2 объединяются в состояние А, состояния 3, 5, 7 можно объединить, обозначив новое состояние В. Подставляя объединенные состояния и удаляя лишние строки, можно получить более простой эквивалентный автомат. y z А А В В 6 В 4 А 6 6 6 В 1 1 Недостижимые состояния Среди состояний автоматы могут быть такие, которые недостижимы из начального состояния ни для какой входной последовательности. Такие состояния называются недостижимыми. Строки, соответствующие этим состояниям, можно удалить из таблицы переходов, получив тем самым таблицу переходов автомата, который эквивалентен исходному, но имеет меньшее количество состояний. Для V любого заданного автомата можно составить список достижимых состояний. Для этого необходимо выполнить следующие действия: 1. Начать список начальным состоянием. 2. Для каждого состояния, уже внесенного в список, добавить все ещё не занесенные в него состояния, которые могут быть достигнуты из этого нового состояния под действием одного входного символа. Если эта процедура перестает давать новые состояния, то все достижимые состояния получены, а все остальные состояния можно удалить из автомата. Так как на каждом шаге процедуры к списку достижимых состояний добавляется хотя бы одно новое состояние, число шагов процедуры ограничено числом состояний данного автомата. S0 S1 S2 S3 S4 S5 S6 S7 S8 S1 S2 S2 S5 S5 S3 S8 S0 S3 1 S5 S7 S5 S7 S6 S1 S0 S1 S0 1 1 1 1 S0 S1 S2 S3 S5 S6 S7 S8 S1 S2 S2 S5 S3 S8 S0 S3 1 S5 S7 S5 S7 S1 S0 S1 S0 1 1 1 1 S0 S1 S2 S3 S5 S7 S1 S2 S2 S5 S3 S0 1 S5 S7 S5 S7 S1 S1 1 1 1 Если начать из состояния S0, то видно, что состояния S1 и S5 достигаются под действием одного входного символа. Из состояния S1 есть переход в S2 и S7; из состояния S5 – в S3 и S1. Таким образом, получается, что S0, S1, S5, S2, S7 и S3 – достижимы, и нужно проверить, есть ли переходы в какие-либо новые состояния из S2, S7 и S3. Проверка показывает, что никакие новые состояния не достигаются, поэтому S4, S6 и S8 – недостижимы. Их можно удалить из таблицы, получив эквивалентный автомат. Приведенные автоматы Автомат называется приведенным, если он не содержит недостижимых состояний, и никакие два его состояния не эквивалентны друг другу. Если автомат не является приведенным, то можно получить эквивалентный ему автомат с меньшим количеством состояний путем выбрасывания недостижимых состояний и объединения двух эквивалентных состояний в одно. Процесс приведения можно повторять до тех пор, пока не получится приведённый автомат. Отсюда следует, что для каждого конечного автомата эквивалентный ему приведённый автомат. Приведённый автомат имеет меньшее количество состояний и может быть более компактно реализован. Приведённые автоматы будут эквивалентны исходным, за исключением имен, которыми названы их состояния. Произвольный конечный автомат можно превратить в эквивалентный ему минимальный автомат, выбрасывая недостижимые состояния и объединяя эквивалентные состояния. Минимальные конечные автоматы используются в большинстве приложений с целью минимизации затрат памяти. ЛЕКЦИЯ № 9 Недетерминированные автоматы Недетерминированный автомат был определен выше как автомат общего вида, у которого значениями функции переходов являются множества состояний, а не отдельные состояния, и вместо одного начального состояния автомата задаётся множество начальных состояний. Для таких автоматов функция переходов δ имеет вид δ: Q×∑→P(Q); где P(Q) – множество всех подмножеств Q, а вместо одного начального состояния может быть задано множество таких состояний. Пример: Q{A,B,C}; ∑={0,1}, q0={A,B}; F={B,C} Функции переходов δ(A,0)={A,B}; δ(B,0)={B}; δ(C,0)={} δ(A,1)={C}; δ(B,1)={C}; δ(C,1)={A,C} А, B 1 Начальные состояния принято помечать C 0 стрелками. Последовательность 11 – одна из B C 1 допускаемых автоматом, так как , причём В – начальное состояние, а С – А, C 1 допустимое. Существование одной этой C последовательности переходов достаточно для того, чтобы показать допустимость входной последовательности 11, и существование другой последовательности переходов из начального состояния в отвергающее, например: (А – отвергающее состояние) на это не влияют. Поэтому, входная последовательность длины n допускается недетерминированным автоматом тогда и только тогда, когда можно найти последовательность состояний S0, S1, …, Sn такую, что S0 – начальное состояние, Sn – допускающее состояние, и для всех i таких, что 0 < i ≤ n, состояние Si Є множеству новых → А → В состояний, приписанных функцией переходов состоянию Si-1 для iго элемента входной последовательности. В рассмотренном примере один из переходов недетерминированного автомата, а именно, δ(С,0) является переходом в пустое состояние. Это означает, что для состояния С и входного символа 0 дальнейшие переходы невозможны. Такой элемент таблицы переходов может препятствовать существованию последовательности переходов для некоторой последовательности. В данном примере такой последовательностью является 10, так как символ 1 переводит оба начальных состояния в состояние С, множество преемников которого пусто. Такие входные последовательности просто отвергаются наряду со всеми прочими последовательностями, которые не могут перевести начальное состояние в заключительное. Работу недетерминированного автомата можно интерпретировать двумя способами. Пусть автомат находится в состоянии А, и к нему применяется входная последовательность, начинающаяся с 0. Тогда можно представить себе один из следующих вариантов: 1. Автомат осуществляет выбор, переходя либо в А, либо в В, т.е., в одно из новых состояний, соответствующему старому состоянию А и входному символу Q. Автомат продолжает работать подобным образом, и при этом возникает много выборов. Если имеется какая-либо последовательность выборов, при которой автомат под действием входной последовательности заканчивает работу в допустимом состоянии, то эта входная последовательностей допускается автоматом. Достаточно только одной последовательности выборов, приводящей к допустимому состоянию, чтобы автомат допускал данную входную последовательность, даже если много других последовательностей выборов, не ведущих к допустимому состоянию. 2. Автомат распадается на два автомата, один из которых находится в состоянии А, а другой – в состоянии В. При продолжении обработки входа происходит дальнейшее деление каждого вновь полученного автомата в соответствии с возможностями, содержащимися в таблице переходов. Когда очередной входной символ обработан, входная последовательность допускается, если один из результирующих автоматов находится в допустимом состоянии. Эти две интерпретации эквивалентны. Назначение недетерминированного автомата – определение допустимого множества входных последовательностей. Пример. Недетерминированный автомат с входным алфавитом {А, Л, Н, О, С, Ь}, который допускает только две последовательности ЛАССО и ЛАНЬ. 1. Определение состояний: С0 – некоторое начальное состояние; Состояние Л1 – Л в слове Лассо Состояние А1 – А в Н С Л О А Ь слове Лассо Л1Л С1 – первое С в слове С0 2 Лассо А1 С2 – второе С в слове Л1 А1 С1 Лассо С1 С2 О – О в слове Лассо С2 О Л2 – Л в слове Лань О 1 А2 – А в слове Лань Л2 А2 Н – Н в слове Лань А2 Н Ь – Ь в слове Лань Н Ь 0 Ь 1 Недетерминированные автоматы проявляются двояко. Вопервых поскольку оба Л из Лассо и Лань могут встречаться сразу после начального состояния, Л1 и Л 2 оба помещаются в соответствующий элемент таблицы. Во-вторых, встречается буква, которая не может быть правильным продолжением слова и эти места просто оставляются незаполненными, как указание на то, что продолжение невозможно, что сигнализирует о состоянии ошибки. Эквивалентность недетерминированных и детерминированных конечных автоматов Для каждого недетерминированного конечного автомата существует детерминированный конечный автомат, который допускает в точности те же входные последовательности, что и недетерминированный. Основная идея нахождения такого автомата заключается в том, что после обработки отдельной входной последовательности состояние детерминированного автомата будет представлять собой множество всех состояний недетерминированного автомата, которые он может достичь из начальных состояний после применения данной последовательности. Переходы детерминированного автомата можно получить из переходов недетерминированного автомата, вычисляя множество состояний, которые могут следовать после данного множества при различных входных символах. Допустимость последовательности определяется по тому, является ли последнее детерминированное состояние, которого он достиг, множеством недетерминированных состояний, включающим хотя бы одно допускающее состояние. Результирующий детерминированный автомат является конечным, лишь конечное количество подмножеств так как недетерминированных состояний. Если недетерминированный автомат имеет n состояний, то эквивалентный детерминированный автомат, вообще говоря, может иметь 2n состояний, по числу подмножеств исходного множества состояний. На практике многие из этих подмножеств представляют собой недостижимые состояния. Можно построить процедуру, в соответствии с которой переходы строятся только для тех подмножеств, которые действительно необходимы. Процедура состоит из следующих шагов. Пусть Мн – недетерминированный автомат, а Мд – эквивалентный ему детерминированный автомат, который нужно построить. 1. Пометить первую строку таблицы переходов для Мд множеством начальных состояний Мн. Применить к этому множеству шаг 2. 2. По данному множеству состояний S, помечающему строку таблицы переходов автомата Мд, для которого переходы еще не вычислены, вычислить те состояния Мн, которые могут быть достигнуты из S с помощью каждого входного символа х, и поместить множество всех последующих состояний в соответствующие ячейки таблицы для Мд. Если δ – функция переходов недетерминированного автомата, то функция перехода детерминированного автомата δ' задается формулой: δ'(s, x)={S/s Є δ(t, x) Процедура состоит из следующих шагов. Пусть Мн – недетерминированный автомат, а Мд – эквивалентный ему детерминированный автомат, который нужно построить. 1. Пометить первую строку таблицы переходов для Мд множеством начальных состояний Мн. Применить к этому множеству шаг 2. 2. По данному множеству состояний S, помечающему строку таблицы переходов автомата Мд, для которого переходы еще не вычислены, вычислить те состояния Мн, которые могут быть достигнуты из S с помощью каждого входного символа х, и поместить множество всех последующих состояний в соответствующие ячейки таблицы для Мд. Если δ – функция переходов недетерминированного автомата, то функция перехода детерминированного автомата δ' задается формулой: δ'(s, x)={S/s Є δ(t, x) для t из S} 3. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть имеется ли в М д строка, помеченная этим множеством. Если нет, то создать новую строку и пометить её этим множеством. Если множество уже использовалось как метка, то никаких действий не требуется. 4. Если в таблице автомата Мд есть строка, для которой ещё не выполнены переходы, вернуться назад и применить к этой строке шаг 2. Если все переходы выполнены перейти к шагу 5. 5. Пометить строку как допускающее состояние автомата Мд тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата. В противном случае пометить как отвергающее состояние. 1 {А,В} Пример. →А А,B 1 C →В C B C А,C {А,В} {А,В} {С} 1 1 1 {С} шаг 1 1 {А,В} {А,В} {С} {С} { } {А,С} Применение шага 2 S'({А, В}, 0) ={А,В}, S'({А,В}, 1)={С} Шаг 3: Для {А, В} строка, для {С} – строки получается новая строка. такая конфигурация: 1 {А,В} {А,В} {С} {С} { } {А,С} { } {А,С} 1 {А,В} {А,В} {С} {С} { } {А,С} { } { } { } {А,С} {А,В} {А,С} На шаге 4 обнаруживается, что применить шаг 2 к {С}. на шаге 3 выясняется, что две строки. к {А,В} даёт: уже имеется нет. Для {С} Получается нужно После этого нужны ещё шаг 2 {А,В {А,В } } Применение шага 2 к {А,С} к пустому множеству { } дает переходы в множества, которые уже являются именами состояний. {А,В} {А,В} {С} { } { } { } {А,С} {А,В} 1 {С} {А,С} { } {А,С} 1 1 1 1 {С } Теперь шаг 4 предписывает перейти к шагу 5. Состояние {А,В} отмечается как допускающее поскольку оно содержит допускающее состояние В; состояния {С} и {А,С} отмечаются как допускающее состояние С. Пустое множество, разумеется не содержит допускающего состояния и поэтому помечается как отвергающее. 1 2 3 4 1 3 3 1 1 2 4 3 4 Теперь достаточно просто изменить имена 1 состояний, для того, чтобы упростить автомат 1 окончательно, т.е. получить тот же самый автомат, но в других обозначениях. 1 Можно показать, что эта же процедура, примененная к автомату, распознающему слова «ЛАНЬ» и «ЛАССО», даст автомат следующего вида: Н {С0} {Л1Л2} {А1А2} {С1} {С2} {О} {Н} {Ь} { } С Л {Л1Л2} О А Ь {А1А2} {Н} {С1} {С2} {О} {Ь} 1 1 Теоретически исходный недетерминированный автомат с десятью состояниями может иметь эквивалентный детерминированный вариант с 1024 состояниями, в соответствии с числом подмножеств множества, содержащего 10 состояний. На самом деле потребовалось только девять состояний. Это даже меньше исходного числа состояний. Порождение только необходимых подмножеств – чрезвычайно полезный прием. Большинство переходов приводит к пустому множеству, оно является состоянием ошибки. Оно переходит само в себя для всех входов и имеет место только тогда, когда для данной последовательности нет допустимых продолжений. Состояния {0} и {С} – эквивалентны, и их можно объединить. Лекция №5 Автоматы с магазинной памятью Конечный автомат может решать лишь такие вычислительные задачи, которые требуют фиксированного и конечного объёма памяти. В компиляторе, однако, имеется много задач, которые не могут быть решены при таком ограничении. Поэтому возникает необходимость в применении более сложной модели. Например, задача обработки скобок в арифметических выражениях. Выражение может начинаться с любого количества левых скобок, и компилятор должен проверить наличие в выражении точно такого же количества правых скобок (определение баланса скобок). Для решения этой и других задач компиляции необходимо использование моделей более мощных автоматов. Для получения более мощного автомата память конечного автомата расширяется за счёт дополнительного механизма хранения, одним из которых является магазин, или стек. Символы можно помещать в стек и извлекать их из него. При помещении символа в стек говорят, что он вталкивается в него, при извлечении – символ выталкивается из стека. Стековый автомат, или магазинный автомат принято называть МП-автоматом. МП-автомат задаётся следующей семёркой: A = {Q, ∑, Z, δ, q0, z0, F}, где Q – непустое множество внутренних состояний; qo Є Q – начальное состояние; ∑ – непустое множество входных символов; Z – непустое конечное множество символов стека; zo Є Z – начальный символ стека; δ – функция перехода δ: Q × (∑ U {ε}) × Z→ P(Q×Z), где ε – переход вне зависимости от входного символа. Таким образом, МП-автомат – это устройство, которое обладает следующими свойствами: - число состояний, в которых он может находиться, конечно; - автомат просматривает последовательность входных символов слева направо без возвратов; - имеется стек, в который автомат вталкивает, и из которого выталкивает символы; - переход автомата из одного внутреннего состояния в другое может сопровождаться вталкиванием или выталкиванием символов; - переход из одного внутреннего состояния в другое осуществляется не только в зависимости от входного символа, но и от символа, находящегося на вершине стека. МП-автомат называется МП-распознавателем, если он имеет два выхода: допустить и отвергнуть. Говорят, что последовательности символов входного алфавита допускается распознавателем, если над действием этих последовательностей автомат, начавший работу в начальном состоянии, выполняет последовательность переходов, приводящих к выходу «допустить». В противном случае последовательность отвергается. Схематически МП-автомат можно представить так: входные символы а1 а2 а3 . . . аi . . . аn считыватель стек Конечный набор состояний zi вершина стека z0 дно стека МП-автомат может быть представлен в виде графа, для чего целесообразно ввести дополнительные обозначения, связанные с его спецификой: а – символ «а» допускается, и автомат переходит в новое состояние. а/х – символ «а» допускается, автомат переходит в новое состояние, в стек заносится символ «х». а/-х – символ «а» допускается, если в вершине стека находится символ «х». Автомат переходит в новое состояние, символ «х» удаляется из стека. /х или/-х – вне зависимости от входного символа и без его чтения автомат переходит в новое состояние. Символ «х» заносится/удаляется из стека. Такой переход называется εдвижением. Пример: Автомат для распознавания последовательности вида {0 n 1n/n>0}; то есть, 01; 0011; …, 000 … 111, то есть, множество последовательностей, начинающихся серией нулей, за которой следует серия единиц той же длины. Начальный отрезок последовательности, состоящий из 0, вталкивается в стек. Каждый раз, когда встречается единица, один ноль выталкивается из стека. Последовательность допускается тогда и только тогда, когда по завершению её стек пуст. Если после первого вхождения 1 встретится 0, последовательность сразу отвергается. Для реализации этой схемы удобно завести специальный символ стека, соответствующий входному символу 0.Можно записывать в стек и собственно «0», но введение такого символа (z) позволит избежать возможной путаницы. Кроме того, необходимо «уведомить» автомат об окончании входной последовательности. Для этого вводится специальный символ, например « ». Процесс обработки распадается на две фазы. Первая фаза – фаза «вталкивание». В этой фразе нули, начинающие последовательность вталкиваются в стек. Эти нули представляются символом стека z. Вторая фаза – это фаза выталкивания. При появлении единицы из стека удаляется z. При появлении нуля последовательность отвергается. Чтобы отразить факт нахождения автомата в некоторой фазе, вводится два состояния: S1 и S2, соответствующие этим фазам. Для описания механизма управления автоматом задается множество таблиц, по одной для каждого состояния. Чтобы установить, какое действие должно выполняться для данной комбинации состояния, входа и символа стека, нужно найти управляющую таблицу для данного состояния, а затем по входному символу и символу стека определить нужное действие в выбранной управляющей таблице. Управляющие таблицы для рассматриваемого случая, очевидно, будут иметь вид: S1 1 Действия, представленные в этих таблицах, следующее: «сдвиг» - чтение следующего символа; push (z) – втолкнуть в стек символ z; pop – вытолкнуть символ из стека; status (Si) – переход в состояние Si. означают Следует отметить, что управляющие таблицы – это не таблицы переходов. Для рассматриваемого автомата функции переходов определяется следующим образом: δ (S1; 0/z) = S1; δ (S1; 1) = S2; δ (S2; 1/-z)= S2; δ (S2; 0)= e – состояние ошибки. Граф такого автомата имеет вид: 1/-z 0/z S1 S2 1 e Очевидно, что полученный автомат является детерминированным. S1 – начальное состояние; Q = {S1, S2, e}; z = {z, z0}. Этот же автомат можно построить по-другому, если использовать более сложные операции, чем элементарные push (х); pop. Расширенная операция change – (заменить), заключается в выталкивании верхнего символа стека и последующем выполнении нескольких вталкиваний. Последовательность символов, которые операция change должна помещать в стек, указывается в качестве её аргумента. Пример: change (АВС) – помещение в стек АВС. Это эквивалентно последовательности операций: pop, push (А), push (В), push (С). Автомат, реализующий только элементарные операции, называется примитивным. Эти операции могут быть легко реализованы аппаратно. Однако если МП-автомат взять за основу при разработке программной реализации некоторого алгоритма, эти операции будут неестественно ограниченными. Операция change может рассматриваться как сокращение для последовательности примитивных операций над стеком. Новый МП-автомат использует тот же метод счета, что и предыдущий. Символ стека z вталкивается в стек при каждом появлении на входе символа 0 и выталкивается из него при каждом появлении на входе символа 1. Однако для различения фаз вталкивания и выталкивания используется иная стратегия. В фазе вталкивания в верхней ячейке стека хранится новый символ стека – х. Единственное его назначение – сигнализировать управляющему устройству о том, что автомат находится в фазе вталкивания. Когда встречается первая единица, х выталкивается из стека и автомат начинает сопоставлять символы z и единицы. Наличие операции change позволяет реализовать единственного состояния. этот алгоритм с помощью Операция change используется, когда на отвергнуть вершине стека х, а на входе – 0. За один шаг операция отвергнуть эта выталкивает из стека z0 верхний отвергнуть отвергнуть допустить ненужный символ х, помещает на его место символ для запоминания вхождения 0, а затем помещает в вершину стека другой х, чтобы указать, что автомат по-прежнему в фазе вталкивания. Операция keep выполняется при переходе, на котором х выталкивается из стека и начинается фаза выталкивания. Входной символ «1» удерживается, т.е. сдвига не происходит, и эту 1 можно сопоставить с соответствующим символом стека. x change (zx) сдвиг z отвергнуть 1 pop keep pop сдвиг Перевод с помощью МП-автоматов. МП-автомат называется МП-транслятором если при реализации он порождает выходную последовательность. Чтобы автомат выдавал выходную последовательность, управляющее устройство должно кроме обычных операций над входом, стеком и состоянием, производить операцию на выходе. При отсутствии выходной операции предполагается, что на вход ничего не выдаётся. Если надо выдать последовательность АВ, то в определении соответствующего перехода будет операция out (AB). Пример 2: перевод произвольной последовательности из 0 и 1 в последовательность вида 1n 0m , где n и m – количество 1 и 0 в данной последовательности, например 001110111 → 11111000. Один из способов такого перевода заключается в выдаче единиц сразу при их появлении на входе, а при появлении нулей на входе – помещать их в стек. По концу последовательности автомат выталкивает из стека нули и выдаёт их на выход. Управляющая таблица для автомата с одним состоянием, реализующего этот способ, имеет вид: z0 push (0) сдвиг push (0) сдвиг 1 out (1) сдвиг out (1) keep out (0) keep допустить Начальным состоянием стека будет z0. В данном случае стек служит не для распознания, а только для перевода. Пусть 010 – последовательность конфигураций автомата. Если переход вызывает операцию с выходом, эта операция помещается между конфигурацией вызывающей переход и конфигурацией наступающей после перехода. 1. z0 010 2. z0 0 out (1) 10 3. z0 0 4. z0 0 0 out (0) 5. z0 0 6. z0 7. допустить. ЛЕКЦИЯ № 2 Конечные автоматы Аппарат автоматов лежит в основе многих аспектов теории компиляторов. Под автоматом в рассматриваемом случае понимается некоторая математическая модель, свойства и поведение которой можно изучать и которую можно имитировать в виде машинной программы. Простейшим в теории автоматов является конечный автомат. Он служит управляющим устройством для более сложных автоматов. Помимо того, что они служат основой теории автоматов, конечные автоматы находят непосредственное применение в теории компиляторов, благодаря следующим свойствам: 1. Конечный автомат может решать (по крайней мере, в первом приближении ряд простых задач компиляции, например лексический анализ). 2. Так как при моделировании конечно автомата на ЭВМ обработка одного входного символа требует небольшого количества операций, программа работает быстро. 3. Моделирование конечного автомата требует фиксированного объёма памяти. 4. Существует ряд теорем и алгоритмов, позволяющих конструировать и упрощать конечные автоматы, предназначенные для тех или иных целей. Термин «конечный автомат», в действительности, употребляется в разных смыслах в зависимости от подразумеваемых приложений. Общим во всех этих определениях является то, что они моделируют вычислительные устройства с фиксированным и конечным объёмом памяти, которые читают последовательности входных символов, принадлежащих некоторому конечному множеству. С точки зрения теории компиляторов, выходом автомата является указание на то, допустимой или недопустимой является та или иная цепочка символов. «Допустимой» является синтаксически правильная цепочка. Таким образом, основная функция автоматов в теории компиляторов – это распознавание. Определение: Конечным автоматом называется следующая пятёрка: A=(Ω, ∑, δ, qo, F) где: Ω – непустое множество внутренних состояний; ∑ – непустое множество входных символов; qo Є Ω – начальное состояние; F Є Ω – непустое множество заключительных (конечных) состояний; δ – функция перехода (δ (qтек,х)=qнов; δ: Ω × ∑→P(Ω); qтек ,qнов Є P(Ω) (P(Ω) – множество всех подмножеств Ω) Данное определение отличается от классических: 1. Существует множество конечных состояний. Если автомат переходит в конечное состояние, то считается, что он работу закончил. 2. Не существует выходного алфавита. 3. Автомат может быть недетерминированным, т.е. по одному и тому же входному символу существует несколько переходов. 4. Функция переходов может быть определена не на всём множестве пар (qi; aj), где qi Є P(Ω); aj Є ∑. Примеры автоматов Пример 1. Контроллер чётности нечётности (детерминированный автомат) Входной алфавит ∑={0,1}. Множество состояний Q – (чёт, нечёт); Выходное состояние – нечёт (F Є Q: нечёт). Начальное состояние: если проверяется нечётность, то начальным состоянием qo будет чёт, т.к. на первом шаге количество прочитанных единиц равно 0; Функции переходов: δ (чёт, 0)= чёт; δ (чёт, 1)= нечёт; δ (нечёт, 0)= нечёт; δ (нечёт, 1)= чёт; Чётность меняется тогда и только тогда, когда на вход подается единица. Граф этого автомата имеет вид: 1 чет нечет 1 Выходное состояние достижимо, оно достигается для последовательности, содержащей нечётное количество единиц. Пример 2. Автомат заданный следующей «пятеркой»: ∑ = {a, в, c} δ(qo; а)= qo; } δ(qo; а)={qo, q1} δ(qo; а)= q1; Q = {qo; q1; q2} δ(q1; в)= q1; } δ(q1; в)={q1, q0} δ(q1; в)= qo; δ(q1; с)= q2. F = {q2} Это – недетерминированный автомат, граф которого имеет вид: в а qo в q1 в q2 с Последовательности ас, аавваас, авс и т.д. – допустимы, для данного автомата, так как они переводят его из начального состояния в конечное состояние. Последовательности са, аавва – недопустимы, так как для них либо не определена соответствующая функция перехода (са), либо не переводят автомат в конечное состояние (аавва). Таблица переходов Один из удобных способов представления конечных автоматов – это таблица переходов. Информация в таблице переходов размещается в соответствии со следующими соглашениями: 1. Столбцы помечены входными символами; 2. Строки помечены символами состояний; 3. Элементами таблицы являются символы новых состояний, соответствующих входным символам столбцов и состояний строк; 4. Первая строка помечена символом начального состояния; 5. Строки, соответствующие допустимым выходным состояниям (заключительным), помечены справа 1; а строки, соответствующие отвергающим состояниям, помечены справа 0. Для автомата проверки нечётности таблица переходов имеет следующий вид: 1 чет чет нечет 0 нечет нечет чет 1 Для автомата из примера 2 таблица переходов выглядит следующим образом: qo q1 q2 а в с qo,q1 q1,q0 q2 1 1 Определение 1: Последовательность а1а2а3,…,аn Є ∑ допускается конечным автоматом тогда и только тогда, когда последовательность внутренних состояний q0, q1, q2, …, qn такая, что qi+1 = δ (qi, аi+1) i=0, 1, 2, …, n-1; qn Є F. Тогда для автомата примера 1 допустимыми последовательностями являются: 01, 0111, 0010, и т.п. чёт чёт нечет; чёт чёт нечет чёт нечет. Определение 2: Регулярным множеством называется множество последовательностей, которое допускается некоторым конечным автоматом. Таким образом, множество последовательностей из нулей и единиц с нечетным количеством единиц является регулярным множеством для автомата примера 1. Последовательность длины называется пустой последовательностью. Она обозначается символом ε. Пустую последовательность не следует отождествлять с символом пробела « ». Пустая последовательность часто встречается в теоретических построениях и имеет большое практическое значение. Одним из примеров такой пустой последовательности может послужить «пустой» оператор в теле цикла: for (int i = 0; i < 10; i++); В терминах конечных автоматов это означает, что пустая последовательность, примененная к начальному, или любому другому состоянию некоторого автомата, не вызывает никаких переходов, т. е., оставляет данное состояние неизменным. Отсюда следует, что под действием пустой последовательности, примененной к начальному состоянию, автомат заканчивает работу в этом же состоянии. Пустую последовательность не следует отождествлять с пустым множеством. Пустым, или нулевым, называется множество, не содержащее ни одного элемента. Его принято обозначать символом Ǿ. Пустое множество {} не содержит элементов, а множество {ε} содержит единственный элемент – пустую последовательность. Автомат, с входным алфавитом {0,1}, распознающий пустую последовательность, имеет следующую таблицу переходов: S T T T 1 T T Следует отметить, что ε входного алфавита. 1 сам по себе не является символом