Тема 3. Элементы теории конечных автоматов

⇐ ПредыдущаяСтр 24 из 27Следующая ⇒

Основные определения теории конечных автоматов

Конечным автоматом (просто автоматом) называется система (пятерка):

S = < X, Y, Z, φ, ψ >,

где X = {х1, х2, …, хi} — конечное входное множество (входной алфавит);

Y = {y 1, y 2, …, yj} — конечное множество внутренних состояний автомата (алфавит состояний);

Z = {z 1, z 2, …, zk} — конечное выходное множество (выходной алфавит);

φ — функция переходов (из состояния в другие состояния);

ψ — функция выходов.

Если указанные множества бесконечные, то это уже не конечный автомат.

Если функция переходов вероятностная, то это недетерминированный автомат.

Если в автомате выделено одно состояние, называемое начальным (обычно это y 1), то полученный автомат называется инициальным и обозначается < S, y >. Таким образом, по неинициальному автомату с i состояниями можно i различными способами определить инициальный автомат.

Функция переходов представляет собой отображение вида φ: X × X ↦ Y или в другом виде:

y (t + 1) = φ [x (t ), y (t )],

где x (t ), y (t ), y (t + l ) — конкретные символы алфавитов X и Y соответственно в моменты автоматного времени t, t + 1 (в тактах t и t + 1); y (t ) — текущее внутреннее состояние при соответствующем x (t ); y (t + l ) — последующее внутреннее состояние.

Иначе говоря, функция переходов определяет последующее состояние автомата по заданному текущему и входному символу.

Функция выходов представляет собой отображение вида ψ: X × Y ↦ Z или в другом виде:

z (t ) = ψ [x (t ), y (t )],

где x (t ), y (t ), z (t ) — конкретные символы алфавитов X, Y, Z соответственно. Мы не будем особо выделять последующие значения x (t + 1) и z (t + 1), поэтому зависимость от t будем указывать только для внутреннего состояния, чтобы отделять y (t ) от y (t + l ).

Указанная функция выходов — функция так называемого автомата Мили.

В теории конечных автоматов рассматривается также автомат Мура, у которого функция выходов проще: ψ: X ↦ Y или z (t ) = ψ [y (t )].

Автомат называется комбинационным, если для любого входного символа х и любых состояний уi, yj φ (х, уi) = φ (х, уj) = z, иначе говоря, если выходной символ z не зависит от состояния и определяется текущим входным символом. Говорят, что у такого частного класса автомата все состояния эквивалентны и, следовательно, комбинационный автомат имеет одно состояние. Такой автомат задается тройкой символов:

S = < X, Z, ψ >.

Рассмотрим представление конечного автомата (КА) в виде «черного ящика» (рис. 51).

Рис. 51. Конечный автомат в виде «черного ящика»

В комбинационном автомате внутренних состояний не указывают.

Входное слово — последовательность входных символов.

Выходное слово — последовательность выходных символов, соответствующих входному слову. В конечном автомате также выделяется последовательность символов внутренних состояний, соответствующих входному слову.

Большой вклад в теорию дискретных (цифровых) автоматов внесли отечественные ученые: М.А. Гаврилов, который опубликовал первую в мире монографию «Теория релейно-контактных схем» (1950 г.), В.М. Глушков, В.Н. Рогинский, П.П. Пархоменко, В.Г. Лазарев, С.И. Баранов, А.Д. Закревский, Э.А. Якубайтис, С.В. Яблонский, В.И. Варшавский и др.

Описание конечных детерминированных автоматов
таблицами переходов-выходов и графами

Поскольку функции φ и ψ определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводят в одну, φ × ψ: X × Y ↦ Y × Z и называют таблицей переходов-выходов, или просто таблицей переходов (автоматной таблицей). При задании автомата ориентированным графом (орграфом) его вершины сопоставляют с внутренними состояниями, а дуги — с условиями перехода из состояния в состояние. Дуги помечают входными символами автомата, а также соответствующими выходными символами, если это автомат Мили.

Рассмотрим граф переходов некоторого автомата Мили (рис. 52), X = {х1, х2}, Y = {у1, у2, y 3}, Z = {z 1, z 2, z 3}.

На графе автомата Мили (рис. 52) дуги помечаются дробью, где в числителе — входной символ, а в знаменателе — выходной символ.

Рис. 52. Граф некоторого автомата Мили

Представим этот же автомат Мили таблицей переходов (табл. 51).

Таблица 51

Таблица переходов выходов автомата Мили,
заданного графом, представленным на рис. 52

В клетках табл. 51 записывается дробь, в числителе которой указывается последующее внутреннее состояние y (t + l ), а в знаменателе — выходной символ z (t ). Это указано в специальной выноске таблицы . Видно, что автомат не полностью определенный (клетка у 3х 2не заполнена).

Рассмотрим граф некоторого автомата Мура (рис. 53), X = {х1, х2}, Y = {у1, у2, y 3}, Z = {z 1, z 2, z 3}:

Рис. 53. Граф некоторого автомата Мура

Выходные символы в автомате Мура сопоставляются с конкретными внутренними состояниями и записываются в знаменателе дроби, помечающей внутренние состояния. Само внутреннее состояние указывается в числителе. Дуги графа автомата Мура помечаются только входными символами. Соответствующая этому автомату Мура таблица переходов представлена табл. 52.

Таблица 52

Таблица переходов выходов автомата Мура,
заданного графом, представленным на рис. 53

В клетках табл. 52, соответствующих входным символам, записывается только последующее внутреннее состояние y (t + l ), что указано в специальной сноске (y (t + l )).

Комбинационный автомат задается таблицей истинности (соответствия), уже известной нам, так как граф переходов такого автомата имеет одну вершину и m петель, где m — число входных символов. Пример таблицы истинности, задающей некоторый комбинационный автомат, приведен в табл. 53.

Таблица 53

Таблица истинности комбинационного автомата:

X ={х1, х2, х3, х4}, Z = { z 1, z 2, z 3, z 4}

В отличие от комбинационного конечного автомата, имеющего одно внутреннее состояние, конечные автоматы, имеющие больше, чем одно внутреннее состояние, называются последовательностными конечными автоматами, или просто последователъностными автоматами.

Рассмотрим последовательностный автомат, заданный табл. 54. Зафиксируем начальное состояние y 1и каждому входному слову (последовательности входных символов) поставим в соответствие слово ω в выходном алфавите:

Это соответствие, отображающее входные слова в выходные, называется автоматным отображением.

Таблица 54

Таблица переходов-выходов некоторого автомата Мили

Зададим входное слово а = x1х2х3х4. Тогда выходное слово ω = z 1z 1z 1z 3.

Рассмотрим подробнее процесс формирования выходного слова:

В этой последовательности указаны так называемые переходы из состояния в состояние, обведенные линией. Например, при поступлении х2автомат сначала находится в состоянии y1, а затем переходит в состояние у2. Указанные выше последовательности иногда изображают стрелками в таблице переходов-выходов.

Состояния yjназывают достижимыми из состояния yi, если существует входное слово α, такое, что φ (α, yi) = yj.

Состояния называются эквивалентными, если они соответствуют одинаковым последовательностям «входное слово — выходное слово»; причем длина такой последовательности может быть любая ≥ 1.

Автомат называется сильно связанным, если из любого его состояния достижимо любое другое состояние.

Автомат называется автономным, если его входной алфавит состоит из одной буквы X = {х}. Все входные слова автономного автомата имеют вид хх…х.

⇐ Предыдущая 18 19 20 21 22 232425 26 27 Следующая ⇒