2-Одноленточные конечные автоматы_ответы


5) Одноленточные автоматы. Способы задания. Алгоритм функционирования.
Одноленточный конечный автомат над алфавитом V задается набором A = {V, Q, R, q0, #, I} и правилом функционирования, общим для всех таких автоматов. В наборе АV — входной алфавит (конечное множество допустимых входных символов), из которого формируются слова, считываемые автоматом;
Q — конечное непустое множество состояний (QV=);
R — множество выделенных заключительных состояний (RQ);
q0 — выделенное начальное состояние;
# — «пустой» символ.
I — программа автомата - представляет собой множество команд вида q а q', в которой qQ, q'Q, aV и для любой пары (q, a) существует единственная команда, начинающаяся этими символами. Программу автомата можно рассматривать как функцию δ: Q×V→ Q переходов автомата, которая паре (состояние, символ алфавита) ставит в соответствие новое состояние (состояние перехода).
Полностью определенным называется одноленточный автомат, у которого в программе существует команда для любой пары (q, a). При табличном способе задания полностью определенного автомата заполнена каждая клетка.
Частичным называется одноленточный автомат, у которого в программе не для любой пары (q, a) существует команда. При табличном способе задания частичного автомата некоторые клетки не заполнены.
Детерминированным называется одноленточный автомат, у которого для любой пары (q, a) существует единственная команда, начинающаяся этими символами. При табличном способе задания детерминированного автомата в клетке записано только одно состояние.
Автомат называется пустым, если множество допускаемых им слов пусто (МА = ).
Наглядным способом задания одноленточного автомата является граф автомата
Другим способом задания одноленточного автомата является таблица, в которой строки соответствуют символам алфавита, столбцы — состояниям. В клетке, расположенной в строке a и столбце q записывается состояние q' , если в программе автомата есть команда q а q' . Столбцы, соответствующие заключительным состояниям, отмечаются единицами.
Неформально одноленточный автомат можно представить как абстрактную машину, похожую на машину Тьюринга, но имеющую следующие особенности:
1) выделены заключительные состояния;
2) машина считывает символы с ленты, ничего не записывая на нее;
3) на каждом шаге головка автомата, считав символ с ленты и перейдя согласно программе в новое состояние, обязательно передвигается вправо на одну клетку;
4) автомат останавливается в том и только в том случае, когда головка достигнет конца слова, т.е. символа .
6) Минимальные одноленточные автоматы. Алгоритмы минимизации.
Автомат, имеющий наименьшее количество состояний по отношению ко всем другим автоматам, ему эквивалентным, называется минимальным. Автомат минимален, если в нем нет состояний, не достижимых из начального, и нет ни одной пары эквивалентных состояний. Состояния, недостижимые из начального, не участвуют в работе автомата, поэтому их можно исключить из множества состояний, а команды, содержащие такие состояния, исключить из программы. При задании автомата графом, вершины, соответствующие недостижимым состояниям, можно удалить вместе с инцидентными дугами. При табличном способе задания автомата можно удалить столбцы, соответствующие недостижимым состояниям.
Для получения минималиного автомата (минимизации автомата) можно использовать следующий алгоритм.
1. Пока в автомате есть хотя бы одна пара эквивалентных состояний, исключить одно из состояний пары описанным выше способом.
2. Исключить все состояния, недостижимые из начального. Для поиска множества недостижимых состояний можно найти множество достижимых состояний, используя алгоритм поиска в графе (например, в глубину или в ширину), и вычесть его из множества состояний автомата.
Для минимизации автомата можно использовать и другой алгоритм, основанный на разбиении множества состояний на классы эквивалентных состояний и замене каждого класса одним состоянием (объединении класса эквивалентных состояний в одно состояние).
Для разбиения множества состояний на классы эквивалентных состояний используется понятие k-эквивалентных состояний. Определим множество как множество всех слов длины k, допускаемых состоянием q. Состояния qi и qj называются k-эквивалентными, если . Множество всех k-эквивалентных между собой состояний образует класс k-эквивалентных состояний. Для нахождения разбиения множества состояний на классы эквивалентных состояний последовательно определяются разбиения на классы 0-, 1-, …, k-эквивалентных состояний. Процесс заканчивается, когда на некотором шаге классы k-эквивалентных состояний совпадут с классами (k – 1)-эквивалентных состояний. В этот момент разбиение на классы k-эквивалентных состояний будет представлять собой разбиение на классы эквивалентных состояний.
7) Эквивалентность одноленточных автоматов.
Автоматы A1 и A2 эквивалентны, если равны множества допускаемых ими слов, т. е. .
Алгоритм проверки эквивалентности двух состояний основан на следующем факте:
состояния q и q' эквивалентны тогда и только тогда, когда выполня-ются следующие два условия:
1) условие подобия — состояния q и q' должны быть либо оба заключительными, либо оба незаключительными;
2) условие преемственности — для всех символов алфавита состояния q и q' должны переходить в эквивалентные состояния.
В процессе выполнения алгоритма строится дерево проверки эквивалентности состояний, в вершинах которого записываются пары состояний (в корне – пара проверяемых на эквивалентность состояний), а дуги отмечаются символами алфавита. Вершины строящегося дерева определяются как внутренние, граничные, дублирующие, конечные или различающие. Граничная — это вершина, являющаяся листом и еще не обработанная алгоритмом. После обработки эта вершина станет либо внутренней, имеющей сыновей, либо дублирующей, либо конечной, либо различающей. Дублирующая — это вершина, являющаяся листом и содержащая такую пару состояний, которая есть хотя бы в одной из внутренних вершин. Конечная — это вершина, которая содержит два одинаковых состояния. Различающая — это вершина, которая содержит заключительное и незаключительное состояние.
Алгоритм проверки эквивалентности двух состояний следующий.
1. Построить вершину — корень дерева, записать в нее пару проверяемых состояний. Если в корне одно состояние заключительное, а другое незаключительное, то пара проверяемых состояний является неэквивалентной (нарушено условие подобия), конец алгоритма. В противном случае корень считать граничной вершиной и выполнить п.2.
2. Пока есть граничные вершины, обрабатывать их в порядке построения следующим образом.
Для каждого символа алфавита создать вершину, в которую провести дугу, отмеченную этим символом, из обрабатываемой вершины; в созданную вершину записать состояния переходов из состояний, записанных в обрабатываемой вершине, при обработке символа, отмечающего входящую дугу.
Если в созданной вершине одно состояние заключительное, а другое — нет, то сделать эту вершину различающей; пара проверяемых состояний является неэквивалентной, конец алгоритма.
Если в созданной вершине содержится такая пара состояний, которая есть хотя бы в одной из внутренних вершин, то сделать эту вершину дублирующей.
Если в созданной вершине содержится пара одинаковых состояний, то сделать эту вершину конечной.
В остальных случаях созданную вершину считать граничной.
Обработанные граничные вершины считать внутренними.
3. Если в множестве вершин дерева нет различающей, то пара проверяемых состояний является эквивалентной, конец алгоритма.
Если в результате выполнения алгоритма построено дерево, в котором нет различающей вершины, то все пары состояний, записанные в вершинах дерева, являются эквивалентными. Если же в результате выполнения алгоритма построено дерево, в котором есть различающая вершина, то неэквивалентными будут все пары состояний, записанные в вершинах на пути от корня к различающей вершине (для них не выполняется условие преемственности). Слово, соответствующее пути от корня к различающей вершине, представляет собой слово, различающее проверяемые на эквивалентность состояния, причем это будет кратчайшее из различающих состояния слов, т.к. дерево проверки строится в ширину.

Приложенные файлы

  • docx 15866897
    Размер файла: 26 kB Загрузок: 0

Добавить комментарий