Автоматы можно рассматривать как механизмы, состоящие из:
блока управления, который может пребывать в различных состояниях ( S внутренний алфавит);
входного канала;
выходного канала.
Входной канал считывает входные сигналы ( Х ) из внешней среды. Выходной канал выдает выходные сигналы ( Y ) во внешнюю среду. Работа автомата протекает в дискретные такты времени t =1,2,3,…. По команде в некотором такте времени блок управления установлен в состоянии и входной канал воспринимает , тогда в этом же такте в выходной канал выдается символ , а к следующему такту +1 блок управления перейдет в состояние .
Определение. К.Д.А. называется система , где — алфавит состояний, – входной алфавит, – выходной алфавит. Множества S , X , Y – конечные.
Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным .
4.2 Способы задания автоматов.
Таблица переходов–выходов.
С помощью орграфов. Вершины граф означают состояния, а дуги – переходы между ними. Из каждой вершина исходит k дуг. Из вершины проводится дуга в вершину в том и только в том случае, когда для некоторого .
Этой дуге приписывается пометка :
Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.
С помощью канонических уравнений:
в момент t =1 автомат находится в начальном состоянии . В каждый момент t =1,2,3,… дискретного времени автомат, находясь в некотором состоянии s ( t ) из множества S , под действием входного сигнала выдает выходной сигнал из множества Y , согласно функции выходов l , а затем меняет свое состояние на s ( t +1) согласно функции переходов d .
Для определения множества состояний автомата необходимо уяснить содержательный смысл и назначение понятия состояния.
После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях , , ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом «запомнить». В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t .
Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:
Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:
И –начальное состояние.
Построим таблицу переходов–выходов:
Для нарисуем диаграмму Мура:
И дополним таблицу переходов–выходов:
4.3 Эквивалентные состояния. Минимизация к.д.а.
Определение. Две диаграммы Мура называются изоморфными , если они могут быть превращены одна в другую переобозначением вершин.
Определение. Два автомата называются изоморфными , если их диаграммы Мура изоморфны.
Рассмотрим два автомата и с одинаковыми входным и выходным алфавитами.
Определение. Состояния и называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого входного слова х результат работы автомата такой же, как и для .
В частном случае, когда = , то речь идет о неотличимых состояниях одного автомата.
Определение. Автоматы и называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого состояния найдется эквивалентное ему состояние и обратно.
Неотличимые автоматы осуществляют одно и то же отображение входных слов в выходные.
Определение. Автомат А называется приведенным , если в нем нет эквивалентных (неразличимых) состояний.
Число состояний в приведенном автомате минимально . Для любого автомата существует эквивалентный ему приведенный автомат А . Процедура нахождения такого автомата называется минимизацией автомата .
4.4 Алгоритм минимизации конечного автомата.
Шаг 1 : два состояния s и t относим в один класс , если для любого входного символа x значение функции выхода s совпадает со значениями функции выхода t . В результате получим r классов:
Шаг k : два состояния s и t из одного класса , полученного на предыдущем шаге, относим в один класс , если для любого значения входного символа значения функций состояний принадлежат одному и тому же классу из предыдущего шага. Если шаг k не изменяет разбиения, то процесс останавливается. Доопределяем функции перехода и выхода и строим таблицу переходов –выходов.
Шаг 1: Первое, третье и четвертое состояния отнесем в один класс состояний, а второе, пятое и шестое – в другой:
Шаг 2: Выпишем значения функции переходов для состояний из класса :
Видно, что 1 и 3-е состояния относим в один класс этого шага , а четвертое состояние – в другой . Проанализировав аналогичным образом значения функции выходов для состояний из класса , видим:
; ; , т.е. все они остаются в одном классе. В результате получим разбиение на классы:
Шаг 3: ; ; . Дальнейшего разбиения классов не происходит, поэтому процесс останавливается. Класс назовем состоянием , класс состояний назовем состоянием , а класс – состоянием .
Построим таблицу переходов–выходов:
Построенный автомат – минимальный.
4.5 Каноническая таблица. Канонические уравнения.
Реализация К.Д.А. осуществляется на основе канонических уравнений, которые находятся с помощью канонической таблицы. Каноническая таблица строится следующим образом по таблице переходов–выходов или диаграмме Мура.
Аргументы функций l и d находятся в столбцах слева, а справа – их значения.
Теория вычислений. Введение в конечные автоматы
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
По горизонтали вверху находятся возможные входные символы.
По вертикали слева находятся текущие возможные состояния.
Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.
Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.
Стартовое состояние — состояние откуда КА начинает свою работу.
Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.
Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.
НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.
Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.
Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.
Множества состояний — в один момент времени НКА может находится в нескольких состояниях.
Заключительное состояние обозначается двойным кругом.
В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.
Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.
Для преобразования НКА в ДКА используется алгоритм Томпсона. При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.
Конечные автоматы с магазинной памятью (pushdown automaton)
Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).
Удаление символа из стека — при любом переходе решается какой символ вытолкнуть, если на вершине стека не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стеке, то он добавляется вместе с добавляемыми символами.
Добавление символов в стек — при любом переходе решает какие символы добавить в стек.
Детерминированные — к нему применяются те же правила как к ДКА к тому же завершает работу только в заключительном состоянии.
Недетерминированные — к нему применяются те же правила как к НКА к тому же он может завершать работу в заключительном состоянии или когда стек станет пуст.
Шаблон: входной_символ; удаляемый_символ/добавляемый символ. На дно стека добавляется символ $ для, того, что понять когда он закончился.
Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.
ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.
Машина Тьюринга (Turing machine)
Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.
Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.
Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.
Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.
Если находится в состоянии 1 и прочитан нуль, записать единицу, сдвинуть вправо и перейти в состояние 2.
Если находится в состоянии 1 и прочитана единица, записать нуль, сдвинуть влево и перейти в состояние 1.
Еcли находится в состоянии 1 и прочитан пустой квадратик, записать единицу, сдвинуть вправо и перейти в состояние 2.
Если находится в состоянии 2 и прочитан нуль, записать нуль, сдвинуть вправо и остаться в состояние 2.
Если находится в состоянии 2 и прочитана единица, записать единицу, сдвинуть вправо и остаться в состояние 2.
Если находится в состоянии 2 и прочитать пустой квадратик, записать пустой квадратик, сдвинуть влево и перейти в состояние 3.
ДМТ эквивалентен НМТ, так, что они тоже не различаются.
Универсальная машина Тьюринга (universal Turing machine)
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
Память порождаемой машины не может быть больше, чем у самой УМТ.
Нужно уметь правильно разделять пространство ленты между порождаемой машиной и УМТ, ведь их данные находятся на одной ленте.
На этом введение в автоматы закончено, теперь вы можете продолжить изучать дальнейший материал сами.
Конечные автоматы в языках программирования
Одной из наиболее важных задач, решаемых в теории формальных языков, является следующая.
Пусть задана некоторая порождающая грамматика с терминальным алфавитом и цепочка в алфавите . Спрашивается: принадлежит ли цепочка языку, порождаемому грамматикой ? Эту задачу называют проблемой принадлежности для грамматики . В теории формальных языков доказывается, что проблема принадлежности разрешима для КЗ-грамматик и для КС-грамматик, но в общем случае не разрешима для грамматик типа 0. Решение проблемы принадлежности состоит в разработке распознающего алгоритма, который для произвольных грамматики (из заданного класса грамматик) и цепочки за конечное число шагов выдает ответ на поставленный выше вопрос. В основе подобного рода алгоритмов лежит математическая модель языка, называемая распознающей моделью или анализирующей моделью и являющаяся как бы зеркальной к порождающей модели, примером которой служит порождающая грамматика. Традиционно анализирующие модели языков называют автоматами. В каждом классе языков может быть определена пара порождающая модель — анализирующая модель» или, другими словами, пара «грамматика — автомат», где автомат в определенном смысле анализирует (распознает) цепочки, порождаемые грамматикой.
Неформально автомат можно описать как устройство, состоящее из блока управления, входной ленты, головки автомата и блока внутренней памяти автомата (рис. 7.2). На ленте, которая предполагается полубесконечной (не ограниченной справа) и разделена на ячейки, записываются цепочки во входном алфавите (обозначаемом далее ) так, что буквы цепочки занимают последовательно, начиная с первой и без пропусков, ячейки ленты — по одной букве в каждой ячейке. Цепочку, записанную таким образом на входной ленте автомата, будем называть входной цепочкой. Блок управления может в каждый момент времени находиться в одном из конечного множества состояний (обозначим его через ), а головка может быть установлена в точности на одну ячейку входной ленты. В таком случае говорят, что автомат обозревает данную ячейку.
Автомат, читая входную цепочку, работает по шагам (или по тактам). Пусть в некоторый момент времени автомат обозревает какую-то ячейку ленты, а блок управления находится в некотором состоянии . Такт работы автомата состоит в том, что в зависимости от содержимого обозреваемой ячейки, состояния , а также содержимого внутренней памяти автомат сдвигает головку вправо или влево на одну ячейку либо оставляет ее на прежнем месте, его блок управления переходит в некоторое новое состояние (возможно, что это состояние совпадет с исходным состоянием ), а содержимое внутренней памяти определенным образом модифицируется. В общем случае автомат может и поменять содержимое той ячейки ленты, которую он обозревает (т.е. автомат может работать с лентой или только в режиме чтения, не меняя ее содержимого, а лишь определенным образом продвигая головку, или в режиме чтения/записи).
Вводят понятие конфигурации автомата: она определяется состоянием блока управления, содержимым обозреваемой ячейки и содержимым внутренней памяти*. Автомат в общем случае не является детерминированным устройством, т.е. для него из заданной конфигурации возможны переходы в несколько различных конфигураций. Правила, согласно которым автомат переходит из одной конфигурации в другую, составляют в совокупности его систему команд автомата. Каждая команда разрешает переход из некоторой конфигурации в какую-то другую конфигурацию. Это напоминает игру, например шахматную, когда из текущей позиции на доске можно, сделав ход, получить новую позицию — одну из множества всех позиций, в которые можно попасть из текущей позиции, сделав ход согласно правилам игры. В данном случае правила игры аналогичны системе команд, а позиция на доске — конфигурации автомата.
*Для автоматов конкретных классов понятие конфигурации несколько модифицируется: так, например, в конфигурацию входит не только символ обозреваемой ячейки, но и вся подцепочка входной цепочки, включающая символ обозреваемой ячейки и все символы справа от него.
Автоматы классифицируются в соответствии со структурой своей внутренней памяти, с режимом работы с лентой (только чтение или чтение/запись), а также с типом движения головки по ленте (одностороннее, двусторонее, число ячеек, на которые за один такт можно сдвинуть головку). Множество команд предполагается конечным, т.е. автомат, как и грамматика, имеет конечное описание.
Представим теперь следующую ситуацию. Пусть на входной ленте автомата записана некоторая цепочка . Допустим также, что среди состояний блока управления выделено некоторое специальное состояние, называемое начальным, а также некоторое подмножество состояний, которые называются заключительными.
В начальный момент времени блок управления находится в начальном состоянии, головка обозревает первую (крайнюю левую) ячейку ленты, в которой записан первый символ входной цепочки . Читая цепочку и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии (точнее говоря, в этом состоянии окажется блок управления). Если это состояние является заключительным, то тогда говорят, что автомат допустил цепочку . Спрашивается: каким образом посредством грамматики можно описать множество всех цепочек в алфавите , которые автомат допускает?
Оказывается, что каждому классу грамматик соответствует свой класс автоматов, причем для каждой грамматики соответствующего класса может быть построен автомат, который допускает цепочки, порождаемые данной грамматикой, и только их. Образно говоря, в каждом классе языков возникает пара «писатель — читатель»: грамматика, как «писатель», порождает определенное множество «текстов» (цепочек в заданном алфавите), а «читатель» (автомат) проверяет «правильность» этих текстов, допуская те и только те цепочки, которая порождает «его» грамматика. В качестве «писателя» может выступать программист, пишущий тексты компьютерных программ, а в качестве «читателя» — системные программы, обеспечивающие проверку правильности написанного текста (соответствия его грамматике того или иного языка программирования). Тем самым допускающий автомат становится прообразом некоторого распознающего алгоритма, решающего проблему принадлежности в том или ином классе грамматик.
Заметим, однако, что автомат сам по себе еще не является таким алгоритмом и что оказывается, например, в классе грамматик типа 0 в общем случае построить алгоритм для решения проблемы принадлежности невозможно, хотя автоматы, соответствующие грамматикам типа 0, существуют (так называемые машины Тьюринга). Некоторые вопросы, связанные с переходом от анализирующей модели языка к алгоритму, который решает проблему принадлежности для грамматики, порождающей этот язык, рассмотрены в последующих лекциях.
Мы начинаем с простейших анализирующих моделей — конечных автоматов. Конечные автоматы — это анализирующие модели для регулярных языков. Конечный автомат не имеет внутренней памяти, головка движется по ленте только вправо — на одну ячейку за такт. С ленты можно только читать. Кроме того, автомат может переходить «спонтанно» из одного состояния в другое, не читая ленту и не продвигая головку. Такой такт можно рассматривать как переход из состояния в состояние по пустой цепочке. Его называют λ-тактом.
Итак, из каждого состояния автомат может переходить в другое состояние, читая тот или иной символ входной цепочки, или делать переход по пустой цепочке, причем принимается по определению, что эти два типа переходов исключают друг друга. Поведение конечного автомата определяется его системой команд, в которой каждая команда задается записью
что означает: «из состояния по символу или по пустой цепочке (тогда ) можно перейти в состояние » (возможно, что ).
При этом по определению принимается, что переход по пустой цепочке и переход по входному символу исключают друг друга. То есть для любой пары состояний конечного автомата имеет место следующее: если существует команда (7.4) при , то нет ни одной команды (для такой же пары состояний) при и наоборот.
Конфигурация конечного автомата определяется как упорядоченная пара , где — состояние блока управления, — символ в обозреваемой ячейке, — цепочка во входном алфавите, расположенная в ячейках справа от обозреваемой (цепочку ау принято называть непрочитанной частью входной цепочки). При этом если обозреваемая ячейка пуста, т.е. не содержит какого-либо символа входного алфавита, то непрочитанная часть входной цепочки считается пустой цепочкой.
Чтобы дать математическое определение конечного автомата, нужно заметить, что он, в свете только что изложенного неформального описания, допускает естественную интерпретацию в терминах размеченных ориентированных графов. Будем рассматривать состояния блока управления конечного автомата как вершины ориентированного графа, множество дуг которого определяется системой команд следующим образом: дуга ведет из состояния в состояние (для данных состояний и ) тогда и только тогда, когда в системе команд автомата есть команда (7.4), т.е. возможен переход из состояния в состояние . Каждая дуга имеет метку, которая является либо множеством букв входного алфавита, либо пустой цепочкой.
Метка дуги есть пустая цепочка , если из в можно перейти по пустой цепочке; в противном случае метка дуги есть множество всех входных символов, по которым возможет переход из состояния в состояние .
Пример 7.7. Зададим конечный автомат с входным алфавитом и множеством состояний такой системой команд:
По этой системе команд построим размеченный ориентированный граф, изображенный на рис. 7.3. Среди состояний автомата выделены начальное состояние и два заключительных состояния и . На рис. 7.4 показана последовательность конфигураций, которую проходит конечный автомат, читая цепочку . Эту цепочку автомат допускает, так как, читая ее, он переходит из начального состояния в одно из заключительных. В формальной записи последовательность конфигураций на рис. 7.4 выглядит так:
Этой последовательности отвечает путь в ориентированном графе, ведущий из вершины в вершину
(под каждой стрелкой подписана буква, принадлежащая метке соответствующей дуги и являющаяся очередной буквой читаемой входной цепочки). Заметим, что, например, находясь в состоянии и обозревая второй от конца цепочки символ, т.е. символ , автомат мог, согласно системе команд, сделать переход в состояние , а не в состояние , но тогда он бы «завис» в состоянии и не смог бы прочитать последний символ записанной на ленте цепочки, т.е. символ , так как среди команд нет такой, которая разрешала бы переход из состояния куда-либо по символу .
Эта ситуация демонстрирует как раз недетерминированность конечного автомата как распознающего устройства: система команд («правила игры») позволяет автомату допустить цепочку («игроку» найти последовательность ходов, ведущую к «выигрышу»), но из этого вовсе не следует, что последовательность конфигураций, которую проходит автомат, читая записанную на ленте цепочку, является единственной. Автомат может «ошибиться», сделав «неправильный» ход. Но и последовательность «правильных» ходов может быть не единственной. Например, читая последний символ цепочки, т.е. символ , автомат мог «выбрать» переход в состояние , которое также является заключительным. Рассматриваемый автомат допускает не всякую цепочку в алфавите . Видно, что ни одна цепочка, которая начинается с префикса , не будет допущена автоматом.
Обозначение пустой цепочки , фигурирующей в виде метки дуги ориентированного графа, который представляет конечный автомат, можно интерпретировать как регулярное выражение, т.е. как регулярный язык, состоящий из одной пустой цепочки (см. замечание 7.4). Поскольку метка дуги, являющаяся множеством букв , может быть также записана в виде регулярного выражения, а именно как сумма , то метку каждой дуги можно считать регулярным выражением определенного вида или, так как мы отождествляем регулярные языки и регулярные выражения, регулярным языком. Это позволяет нам формально определить конечный автомат как ориентированный граф, размеченный над полукольцом регулярных языков. Такое математическое определение конечного автомата весьма удобно: оно дает нам возможность применить при изучении конечных автоматов уже изученные нами алгебраические методы анализа размеченных ориентированных графов.
Итак, математическое определение конечного автомата формулируется следующим образом. Конечный автомат — это ориентированный граф, размеченный над полукольцом регулярных языков в алфавите с выделенной вершиной , которая называется начальной, и с выделенным подмножеством вершин , каждый элемент которого называется заключительной вершиной.
На функцию разметки при этом накладываются следующие ограничения: метка каждой дуги есть либо язык , либо непустое подмножество алфавита .
Вершины графа называют обычно в этом случае состояниями конечного автомата, начальную вершину — начальным состоянием, а заключительную вершину — заключительным состоянием конечного автомата.
Замечание 7.5. Если для какой-то дуги ее метка есть язык , то, поскольку этот язык не является подмножеством алфавита , в этом случае , и, наоборот, если , то исключается, что . Таким образом, два рассмотренных случая для значений функции разметки исключают друг друга, на что и было указано в рассмотренном выше неформальном описании конечного автомата.
На рис. 7.5 изображен конечный автомат, для которого алфавит . Начальное состояние показано входной стрелкой, заключительное — выходной. Метки дуг обычно пишут без фигурных скобок. Разрешена запись меток дуг и в виде регулярных выражений (см. рис. 7.5).
Конечный автомат, таким образом, может быть задан как пятерка:
где — множество состояний автомата; — множество дуг; — функция разметки (весовая функция), причем для каждой дуги ее метка или , при этом подмножество не пусто; — начальное состояние; — подмножество заключительных состояний.
Алфавит называется входным алфавитом автомата , а его буквы — входными символами (или входными буквами) данного автомата.
Замечание 7.6. Конечный автомат определен как ориентированный граф, размеченный над полукольцом регулярных языков, но метка дуги задается не как произвольный регулярный язык, а как язык, состоящий из одной пустой цепочки, либо язык, являющийся подмножеством букв входного алфавита. Это ни в коей мере не противоречит основному определению размеченного ориентированного графа, ибо совершенно не обязательно, чтобы область значения функции разметки совпадала с носителем полукольца. Чисто формально, конечно, можно обобщить определение конечного автомата и допустить в качестве меток дуг произвольные регулярные языки, но, как можно показать, это обобщение не является принципиальным, и такое определение конечного автомата сводится к данному выше определению (см. задачи в конце этой главы). Немаловажно и то, что приведенное формальное определение конечного автомата и задание меток дуг как регулярных языков специального вида согласуются с интуитивным представлением об автомате как об устройстве, которое «побуквенно» читает входные цепочки, переходя из одного состояния в другое. Требование, чтобы такое устройство за один такт анализировало («обозревало») любое, сколь угодно сложное регулярное выражение, не отвечает нашей «вычислительной» интуиции, в соответствии с которой за один такт может быть произведена только простая операция, каковой и является «реакция» автомата на обозреваемый одиночный символ или на пустую цепочку.
Если — дуга автомата и ее метка есть регулярное выражение , то в этом случае будем говорить, что в автомате возможен переход из состояния в состояние по пустой цепочке, и писать . Дугу с меткой будем называть λ-переходом (или пустой дугой).
Если же метка дуги есть множество, содержащее входной символ а, то будем говорить, что в автомате возможен переход из состояния в состояние по символу , и писать .
Для конечного автомата удобно ввести в рассмотрение функцию переходов, определив ее как отображение
т.е. значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке. В частности, это может быть пустое множество.
Понятие функции переходов конечного автомата позволяет дать и математическую интерпретацию системы команд. С этой точки зрения система команд есть просто способ представления конечной функции, а именно функции переходов.
Система команд есть конечное множество команд вида , где и — состояния автомата; — входной символ или пустая цепочка, причем указанная команда тогда и только тогда содержится в системе команд, когда .
Содержательная интерпретация команды была приведена выше. Стрелка , как и в записи правила грамматики, есть «метасимвол». Он не содержится ни в одном из алфавитов, фигурирующих в определении конечного автомата.
Система команд автомата, изображенного на рис. 7.5, приведена ниже:
Используя функцию переходов, конечный автомат можно задавать как упорядоченную пятерку:
где — входной алфавит; — множество состояний; — начальное состояние; — множество заключительных состояний; — функция переходов, заданная в виде системы команд. Как правило, в дальнейшем мы именно так и будем определять конечный автомат.
Конечный автомат называют полностью определенным, если из каждого его состояния по каждому входному символу возможен переход в некоторое состояние, т.е.
Заметим, что в полностью определенном конечном автомате, вообще говоря, могут существовать и переходы по пустой цепочке.
Конечный автомат называется детерминированным, если в нем нет дуг с меткой и из любого состояния по любому входному символу возможен переход в точности в одно состояние, то есть
Конечный автомат называется квазидетерминированным, если в нем нет дуг с меткой и из любого состояния по любому символу возможен переход не более чем в одно состояние, т.е.
Замечание 7.7. Для детерминированного конечного автомата значением функции переходов для любой пары (состояние, входной символ) является одноэлементное подмножество множества состояний. Поэтому естественно понимать функцию переходов детерминированного конечного автомата не как отображение множества в множество , а как отображение множества в само множество состояний . Впредь так и будем рассматривать функцию переходов детерминированного конечного автомата, не оговаривая этого особо.
Согласно общему определению метки пути в размеченном ориентированном графе, метка пути в конечном автомате есть соединение* меток входящих в этот путь дуг (в порядке их прохождения). Таким образом, метка любого пути конечной длины в конечном автомате есть регулярный язык. Отметим, что мы, изучая размеченные ориентированные графы, предполагаем, что рассматриваются только пути конечной длины. Так, для автомата, изображенного на рис. 7.5, метка пути равна соединению языков , что можно записать в виде регулярного выражения , а метка пути может быть задана таким регулярным выражением:
что означает, что эта метка есть множество цепочек .
*Умножением полукольца является соединение языков.
Метку пути конечной длины обозначим через . Здесь — это функция, отображающая множество всех путей конечной длины в размеченном ориентированном графе, в полукольцо . Для пути длины 1 значение , т.е. функция разметки ориентированного графа есть ограничение функции на множество всех путей длины 1.
Если цепочка принадлежит метке некоторого пути — пути, ведущего из вершины в вершину конечного автомата , то говорят, что цепочка читается на пути в или что путь несет цепочку . Пишем , если читается на некотором пути из в . В том случае, когда явно надо указать длину пути, на котором читается цепочка , записываем . Если нужно подчеркнуть, что цепочка читается на некотором пути ненулевой длины из в , то используем запись . В терминах неформального описания конечного автомата любому пути, на котором читается входная цепочка , отвечает последовательность конфигураций, которую проходит автомат, читая посимвольно входную цепочку, записанную на ленте, и продвигая головку на один символ вправо за один такт.
Стоимость прохождения из состояния в состояние есть (согласно общему определению этого понятия в размеченных ориентированных графах) объединение меток всех путей*, ведущих из в , т.е. множество всех таких , что . Это значит, что элемент матрицы стоимостей есть язык
*Здесь объединение понимается как бесконечная сумма замкнутого полукольца всех языков в алфавите , т.е. как точная верхняя грань последовательности языков относительно теоретико-множественного включения.
Говоря об элементе матрицы стоимостей, мы отождествляем обозначение состояния автомата с его номером в некоторой нумерации состояний как вершин ориентированного графа.
В частности, язык конечного автомата есть множество всех цепочек во входном алфавите, читаемых в на некотором пути из начального состояния в одно из заключительных состояний. Другими словами,
где — множество заключительных состояний.
Таким образом, язык конечного автомата есть объединение тех элементов матрицы стоимостей автомата, которые находятся в строке, соответствующей начальному состоянию , и в столбцах, соответствующих всем заключительным состояниям .
Замечание 7.8. Необходимо обратить внимание на одну очень важную вещь. В конечном автомате метка произвольного пути конечной длины есть регулярный язык, поскольку он вычисляется как соединение конечного семейства регулярных языков. Но стоимость прохождения между заданной парой вершин априори не является регулярным языком, так как множество путей, ведущих из одной вершины в другую, может быть бесконечным (каждый путь имеет конечную длину, но множество всех таких путей может оказаться бесконечным, содержать пути сколь угодно большой длины — простейший пример дает петля, по которой можно пройти сколько угодно раз). Поэтому объединение при определении стоимости прохождения между парой состояний конечного автомата мы можем сейчас рассматривать только как операцию замкнутого полукольца всех языков в данном алфавите, а именно операцию вычисления точной верхней грани («бесконечная сумма» в замкнутом полукольце). Но коль скоро элементы матрицы стоимостей уже вычислены, их объединение (в формуле (7.5)), дающее язык конечного автомата, разумеется, конечно. Позже будет доказано, что на самом деле все стоимости в конечном автомате также регулярны.
