Эквивалентность детерминированных и недетерминированных конечных автоматов
Материал из Википедии — свободной энциклопедии
 |
Эту статью следует викифицировать. Пожалуйста, оформите её согласно общим правилам и указаниям. |
 |
Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите её в соответствии с правилами написания статей. |
Содержание |
[править] Детерминированный конечный автомат
Термин «детерминированный» говорит о том, что для всякой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
[править] Определение детерминированного конечного автомата
Детерминированный конечный автомат состоит из следующих компонентов:
- Конечное множество состояний S.
- Конечное множество входных символов Σ.
- Функция переходов, аргументами которой являются текущее состояние и входной символ, а значением новое состояние. Функция переходов обычно обозначается как δ. Представляя автомат в виде графа, δ изображаются отмеченными дугами, соединяющими состояния. Если q— состояние и α— входной символ, то δ (q, α)— это состояние р, для которого существует дуга, отмеченная символом α и ведущая из q в р.
- Начальное состояние s0, одно из состояний в S.
- Множество заключительных, или допускающих, состояний F. Множество F является подмножеством S.
В дальнейшем детерминированный конечный автомат часто обозначается как ДКА. Наиболее компактное представление ДКА— это список пяти вышеуказанных его компонентов: A=(S, Σ, δ, s0, F)
[править] Более простые представления ДКА
Существует два удобных способа описания автоматов.
- Диаграмма переходов, которая представляет собой граф.
- Таблица переходов, дающая табличное представление функции δ. Из нее очевидны состояния и входной алфавит.
[править] Недетерминированный конечный автомат
Недетерминированный конечный автомат (НКА) являются обобщением детерминированного. Недетерминированный конечный автомат-распознаватель может быть двух типов: либо существует переход, помеченный пустой цепочкой ε, либо из одного состояния выходят несколько переходов, помеченных одним и тем же символом.
[править] Определение недетерминированного конечного автомата
Структура НКА в основном повторяет структуру ДКА:
A=(S, Σ, δ, s0, F)
- S есть конечное множество состояний.
- Σ есть конечное множество входных символов (алфавит).
- s0, один из элементов S — начальное состояние.
- F, подмножество S — множество заключительных (или допускающих) состояний.
- Функция переходов δ.
[править] Эквивалентность НКА и ДКА
Теорема: Для любого НКА существует эквивалентный ему ДКА
Пример: Построить ДКА для языка (ab) * a + ab *
- Построим конечный автомат по данному языку (Рис. 1);
Получен автомат с пустыми (ε) переходами.
- Преобразуем НКА с ε - переходами в НКА без ε - переходов (Рис. 2);
ε - замыканием состояния s принадлежащему S, обозначаемым Ξ(s), называется множество всех состояний, которые достижимы из ε без подачи входного сигнала.
Множеству Ξ(s) принадлежат: само состояние s и все те состояния, которые достижимы из s по ε - переходам. Для автомата, изображенного на Рис. 1: Ξн = {н, 1, 2}; Ξ1 = {1, 2}; Ξ2 = {2}; Ξ3 = {3, 4, к}; Ξ4 = {4, к}; Ξ5 = {5}; Ξк = {к}.
Все состояния, достижимые из любого начального без подачи сигнала, также являются начальными. Множество заключительных состояний являются такие ε - замыкания состояний, в которые входят заключительные состояния: из каждого такого состояния без подачи входного сигнала можно оказаться в заключительном состоянии.
Для автомата на Рис. 1 таблица переходов эвкивалентного недетерминированного автомата без ε - переходов имеет вид (Табл. 1)
| a | b | |
|---|---|---|
| ->q0=Ξн={н, 1, 2} | {Ξ3, Ξ5, Ξk} | ø |
| ->q1=Ξ1={1, 2} | {Ξ5, Ξk} | ø |
| ->q2=Ξ2={2} | {Ξk} | ø |
| *q3=Ξ3={3, 4, k} | ø | {Ξ4} |
| *q4=Ξ4={4, k} | ø | {Ξ4} |
| q5=Ξ5={5} | ø | {Ξ1} |
| *q6=Ξk={k} | ø | ø |
Граф переходов этого НКА без пустых переходов представлен на Рис. 2
По сравнению с автоматом на Рис. 1 здесь добавилось новое начальное состояние и два конечных.
- Преобразовать НКА без пустых переходов в ДКА
Полученный в итоге ДКА должен иметь примерно столько же состояний, сколько и НКА, хотя часто содержит больше переходов, в худшем случае наименьший ДКА может содержать 2n состояний, в то время как НКА для того же самого языка имеет всего n состояний.
В данном примере большинство состояний окажутся недостижимыми, поэтому запишем в таблицу переходов только достижимые состояния (Табл. 2)
| a | b | |
|---|---|---|
| ->p0={q0} | {q3, q5, q6} | ø |
| *p1={q3, q5, q6} | ø | {q4, q1} |
| *p2={q1, q4} | {q5, q6} | {q4} |
| *p3={q5, q6} | ø | {q1} |
| *p4={q4} | ø | {q4} |
| ->p5={q1} | {q5, q6} | ø |
По Табл. 2 построим граф для ДКА (Рис. 3)
