2.2 Способы описания

Диаграмма состояний (или иногда граф переходов) – графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого – состояния конечного автомата, дуги – переходы из одного состояния в другое, а нагрузка – символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой должны быть надписаны все они.

Таблица переходов – табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу – один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

 

2.3 Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

#"#" title=Увеличить>#"1.files/image008.gif">

Рисунок 2 – Недетерминированный конечный автомат с пустыми переходами

2. Из одного состояния выходит несколько переходов, помеченных одним и тем же символом (рисунок 3).

Рисунок 3 – Недетерминированный конечный автомат с несколькими переходами

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном детерминированном конечном автомате в худшем случае растёт экспоненциально с ростом количества состояний исходного недетерминированного конечного автомата, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

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

 

2.4 Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет – так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

3. Функциональные модели и блок-схемы решения задачи

Функциональные модели и блок-схемы решения задачи представлены на рисунках 4 – 7.

Условные обозначения:

· cur – текущее слово;

· char – текущий символ;

· text – входное слово;

· funct – функция смены состояний;

· start – начальное состояние;

· end – список конечных состояний.

Рисунок 4 – Функциональная модель решения задачи для функции KA

Рисунок 5 – Функциональная модель решения задачи для функции function1

Рисунок 6 – Функциональная модель решения задачи для функции function2

Рисунок 7 – Функциональная модель решения задачи для функции isOneof