Синтез конечного автомата

21

1. Задание

Для синтеза конечного автомата задана формальная грамматика:

G= <V,W,S,R>, где

V_t={c₁, c₂,,c₁₈}-алфавит терминальных символов;

W_n={S, A, B, C, D, E, F}-алфавит нетерминальных символов;

S - аксиома грамматики;

R - правила грамматики.

2.Построение и преобразование грамматик

2.1 Построение праволинейной грамматики

Грамматика называется праволинейной, если правая часть каждого правила содержит не более одного нетерминала, причем этот нетерминал является самым правым символом. Правила праволинейной грамматики имеют вид:

A>щB, A>щ, щV*, BW, гдеV*-множество всех конечных символов

2.2 Построение автоматной грамматики по праволинейной

Грамматика называется автоматной, если ее правила имеют вид:

A>xB, A>о, xV, BW.

3. Построение недетерминированного конечного автомата

Конечным автоматом S называется формальная система вида S={A,Q, V, д, л}, где A-входной алфавит {a₁, a₂,…,a_m}; Q - алфавит состояний (нетерминальное множество грамматики {g₁, g₂,…,g_m}); V - выходной алфавит; д - функция перехода, которая каждой паре элементов A_i и Q_j ставит в соответствие элемент Q₁; л - функция перехода, которая каждой паре элементов A_i и Q_j ставит в соответствие элемент V₁ выходного алфавита.

Недетерминированным конечным автоматом называется такой автомат, любая клетка таблицы переходов которого имеет более одного состояния. Таблица переходов - таблица, где по строкам располагаются состояния, а по столбцам символы входного алфавита

Клетки таблицы заполняются состояниями, в которые переходит автомат под воздействием входных символов, а так же символами входного алфавита, с соответствующими реакциями автомата на входные символы.

Используя правило вывода, строим недетерминированный конечный автомат.

K - заключительное состояние

4. Приведение недетерминированного конечного автомата к детерминированному виду

Детерминированным конечным автоматом называется такой автомат, любая клетка таблицы переходов которого не содержит более одного состояния.

Приводим недетерминированный конечный автомат к детерминированному конечному автомату. Для этого используем следующую процедуру:

1. Определим клетку, которая содержит два перехода

2. Строки состояний накладываются друг на друга, и в таблице появляется новая строка, которая будет соответствовать новому состоянию

3. Если одно из состояний отдельно или в другой из комбинаций в какой-либо клетке таблицы, то соответствующие строки сохраняются в таблице, иначе они удаляются.

5. Минимизация состояний автомата

Минимизация состояний автомата осуществляется по алгоритму Мура:

1) В таблице переходов отыскиваются строки, у которых имеются рабочие состояния в одинаковых столбцах (состояния отличные от состояния ошибки). Состояния таких строк заносятся в группы.

2)Рабочее состояние для каждой группы проверяется на эквивалентность.

3)Если для всех рабочих состояний группы установили эквивалентность, то состояние образующее группу также эквивалентно.

r₇ - аксиома

r₁₀ - заключительное состояние

Минимизированный детерминированный конечный автомат:

6. Построение сети Петри

Сеть Петри определяется как формальная система, характеризуема 4 формальными объектами: S= <P, T, E, M₀>, где

P - конечное множество позиций

T - конечное множество переходов

E - конечное множество дуг

M₀ -- начальная маркировка

Графическим изображением сети Петри является двудольный ориентированный граф с двумя типами вершин Р и Т. Поставим в соответствие нетерминальным символам грамматики позиции сети Петри, а терминальным переходы. Если в правой части некоторого правила имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции.

21

Минимизация сети Петри

21

7. Кодирование состояний автомата

Кодирование автомата определяет обеспечение устойчивости автомата по отношению к состязаниям элементов памяти. Считается, что автомат работает устойчиво, если в процессе его работы не возникает критических состязаний. Критическим считается такое состязание элементов памяти, когда автомат под действием одного и того же входного воздействия может перейти в разные состояния. Поэтому первоочередной задачей кодирования является обеспечение устойчивости автомата.

Существуют два способа кодирования автомата:

1) Характеризуется устранением всех состязаний элементов памяти. Для этого всем внутренним состояниям, для которых существуют переходы приписываются соседние кодовые комбинации, отличающиеся друг от друга одной переменной.

2) Связан с устранением критических состязаний.

21

8. Построение комбинационной схемы таблицы переходов автомата

В качестве структурной схемы распознающего автомата используем следующую схему:

Схема автомата состоит из комбинационной схемы, реализующей функцию возбуждения элементов памяти: памяти, построенной на триггерах по двухрегистровой схеме и дешифратора входных сигналов.

При синхронной реализации автомата предполагается, что все переходные процессы в этих схемах успевают закончиться к моменту прихода синхросигнала t₁, стробирующего (разрешающего) прием информации с выходов комбинационной схемы с триггеров регистра 1. Второй регистр осуществляет прием информации, которая стробируется синхросигналом t₂, необходимым для того, чтобы сделать состояние автомата устойчивым. Триггеры регистра 1 называются вспомогательными, а регистра 2 основными.

Сигнал d_err является сигналом ошибки, а сигнал d_ok - сигналом принадлежности входной цепочки языку заданной грамматики.

z=(z₁, z₂, z₃, z₄)

компоненты вектора - переменные коды состояний;

(p₁ p₂ p₃) - код входного символа.

Комбинационная схема автомата реализует функцию его переходов. Исходным заданием для ее построения является граф переходов или таблица переходов и выбранный вариант кодирования.

Построить функцию переходов - значит найти переключательную функцию кодирующих (внутренних) переменных. Каждая внутренняя переменная z₁, z₂, z₃, z₄ представляется состоянием элемента памяти, то есть триггера. По переключательным функциям внутренних переменных находят функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата.

Таблица переходов автомата по символу x₀

Таблица переходов автомата по символу x₁

Таблица переходов автомата по символу x₂

Таблица переходов автомата по символу x₃

Таблица переходов автомата по символу x₄

Таблица переходов автомата по символу x₅

Таблица переходов автомата по символу x₆

Таблица переходов автомата по символу x₇

9. Построение комбинационной схемы распознавания цепочек языка конечным автоматом

Функция возбуждения сигнала ошибки может быть представлена:

derr= x₀&derr_x0\/ x₁&derr_x1\/…\/x₇&derr_x7

Считаем, что ошибка может возникнуть, когда на x_i срабатывает какое-либо состояние, отличное от состояния заданного таблицей переходов.

Другими словами, при переходе сигнала x_i автомат находится не в тех состояниях, которые ему предписаны таблицей переходов.

Рассмотрим как определить функции распознавания цепочек входного языка, т.е. функцию dok. Очевидно, что dok вырабатывается только тогда, когда на вход автомата пришёл сигнал конца ошибки, а автомат находился в заключительном состоянии.

Таблица функций derr

Анализ таблицы 3 показывает, что в ней больше 1 чем 0. Поэтому удобнее строить логическую функцию для отрицания ошибки d_err._xi . Для каждой функции d_err._xi строим карты Карно и проводим минимизацию слабо определенной функции. На карте проставляем 0 и 1 и рассматриваем функцию как слабо определенную. Затем берем отрицание полученной в ходе минимизации функции.

Комбинационная схема, реализующая функцию переходов автомата

Комбинационная схема, реализующая функцию ошибки derr