Материал на экзамен
.pdfСтруктурная схема автомата представлена на рис. 7.47. Обратим внимание на то, что вместо инверторов для сигналов и мы ис-
пользуем сигналы, снимаемые с инверсных выходов триггеров и
. Заметим также, что переменная оказалась фиктивной. Действительно, тип входного символа («буква», т.е. а или Ь, и «цифра», т.е. 0 или 1) распознается по первому разряду входного вектора : при
имеем « букву», а при — «цифру».
Наконец, следует заметить, что синтезированная «структурная схема», строго говоря, не является графом (поскольку содержит, например,
«кратные дуги», т.е. допускает несколько разных дуг между одной и той же парой вершин). Даже комбинационная часть этой схемы не может быть уже названа схемой из функциональных элементов, так как в вершины, помеченные переменными заходят некоторые дуги. Это будет, говоря неформально, схема из функциональных элементов, «вставленная» в некий более общий «графовый объект».
Минимальная форма автомата
Минимальный автомат — это автомат, имеющий наименьшее возможное количество состояний и реализующий заданную функцию выходов. Задача минимизации автомата сводится к поиску его минимальной формы. Для произвольного конечного автомата может быть построен эквивалентный ему конечный автомат с наименьшим числом состояний.
Принцип построения
Минимальная форма автомата S (обозначается как Š) в теории автоматов представляет собой автомат с ň состояниями, образующими множество {σ1..σň}. Минимальный автомат из S строится следующим
образом. Характеристические функции автоматов S и Š обозначаются gs, gz и g's , g'z соответственно. Тогда, если
, то
.
Таким образом, при построении Š по данному условию не возникает никакой неопределенности.
Алгоритм нахождения минимального автомата был предложен Ауфенкампом и Хоном. Ими было показано, что для нахождения минимального автомата необходимо находить последовательные разбиения Pi
автомата S на классы 1, 2, …, k, (k+1) - эквивалентных между собой состояний, до тех пор пока на каком-то (k+1) шаге не окажется, что Pk
= Pk+1. Таким образом, разбиение Pk дает все классы эквивалентности
состояний автомата S. Всем состояниям S, принадлежащим классу эквивалентности Σl можно приписать общее обозначение, например, σl.
Таким образом, автомат Š получается из автомата S путем «объединения» одинаково обозначенных состояний в одно состояние. Способы, которыми это объединение производится, существенно зависят от того, каким образом определен автомат — таблицей, графом или матрицей.
Способы получения минимальной формы Таблица переходов
Если заданы таблица переходов и эквивалентное разбиение Σ1..Σň
автомата S, то таблица переходов Š может быть построена следующим образом:
1.Заменить обозначение каждого состояния, имеющегося в таблице S на обозначение класса, которому данное состояние принадлежит.
2.Из каждой группы строк с одинаковыми обозначениями в клетках основного столбца вычеркнуть все строки, кроме одной.
Полученная при этом таблица является таблицей переходов Š.
Граф переходов
Если заданы граф переходов (диаграмма состояний) и эквивалентное разбиение Σ1..Σň автомата S, то граф переходов Š может быть по-
строен следующим образом:
1.Заменить обозначение каждого состояния, имеющегося в графе переходов S на обозначение класса, к которому относится данное состояние.
2.Объединить все одинаково обозначенные состояния (рассматривая дуги графа как «гибкие связи») и представить объединенные состояния одним состоянием, имеющим общее обозначение.
3.Из каждой группы дуг, имеющих общее исходное и общее конечное состояние вычеркнуть все, кроме одной.
Полученный в результате граф будет графом Š.
Матрица переходов
Если заданы матрица переходов и эквивалентное разбиение Σ1..Σň
автомата S, то матрица переходов Š может быть построена следующим образом:
1.Провести симметрическую перестановку и симметрическое разбиение [S] так, чтобы строки (и столбцы) группировались соответственно классам эквивалентности S (эту же матрицу можно получить при матричном методе эквивалентного разбиения).
2.Заменить все обозначения строк (и столбцов) каждой группы, представляющей класс эквивалентности, одним обозначением этого класса.
3.Заменить каждую подматрицу в разбитой матрице одной клеткой, содержащей все пары вход-выход, которые имеются в любой строке этой подматрицы (все строки в любой такой подматрице содержат одно и то же множество пар вход-выход).
Полученная в результате матрица является матрицей переходов Š.
Свойства минимальной формы
Если Š является минимальной формой автомата S, то:
1.Š является единственной минимальной формой с точностью до обозначения состояний
2.Š=S
3.Никакие два состояния Š не являются эквивалентными
4.Не существует автомата, эквивалентного S и меньшего (с меньшим числом состояний), чем Š.
Приведенная форма и предваренная нормальная форма предиката
Определение. Формула логики предикатов, в которой из операций логики высказываний имеются только конъюнкция, дизъюнкция и отрицание, причем отрицание относится только к элементарным предикатам, называется приведенной формой предиката.
Теорема 1. Для всякого предиката существует равносильная ему приведенная нормальная форма.
Доказательство. Действительно, все операции в данной предикатной формуле можно выразить через конъюнкцию, дизъюнкцию и отрицание (например, в виде ДНФ). Если после этого некоторые отрицания будут относиться к частям формулы, содержащим кванторы, то отрицания можно «снять» с кванторов согласно равносильностям 1 и 2, а «снять» отрицания с конъюнкций и дизъюнкций можно, следуя законам де Моргана. После всех описанных преобразований предикат, очевидно, будет представлен в приведенной форме.
Определение. Предикатная формула вида , где Кi
– кванторы, хi – различные связанные переменные, а F – предикатная формула без кванторов, находящаяся в приведенной форме, называется предваренной нормальной формой предиката.
Теорема 2. Для всякого предиката существует равносильная ему предваренная нормальная форма.
Доказательство. Согласно теореме 1 можно считать, что предикат уже преобразован в приведенную форму. Если никакая операция навешивания квантора при этом не находится в области действия операций и , то приведенная форма уже является предваренной нормальной. Поэтому предположим, что описанные ситуации имеют место, и будем называть такие явления (когда какой–либо квантор находится в области действия данной операции или ) беспорядками.
Для данной формулы число беспорядков конечно, так как конечно число символов. Выберем какой-либо беспорядок (скажем, первый слева) и покажем, что путем тождественных преобразований его можно убрать. Возможны два случая:
1)Беспорядок имеет вид: x Р или х Р, где Р – не зависит от х. Тогдах или х можно просто отбросить, поскольку хР ≡ Р и хР ≡ Р.
2)Беспорядок имеет вид: хР(х) или хР(х). Если переменная х еще встречается в формуле, то предварительно сделав замену согласно формулам
xP(x) ≡ tP(t), xP(x) ≡ tP(t),
где t – переменная, не встречающаяся в формуле, беспорядок представляется в виде правой части одной из формул 10 – 13. Применяя эти формулы (т. е., заменяя правые части на левые), беспорядок устраняется.
Проделав такие преобразования конечное число раз, все беспорядки будут ликвидированы, что и требовалось доказать.
Пример. Привести к предваренной нормальной форме следующий предикат: