Алгоритм Клинса - Kleenes algorithm - Wikipedia

В теоретическая информатика, в частности в формальная теория языка, Алгоритм Клини преобразует данный недетерминированный конечный автомат (NFA) в регулярное выражение. Вместе с другими алгоритмами преобразования он устанавливает эквивалентность нескольких форматов описания для обычные языки. Альтернативные представления того же метода включают «метод исключения», приписываемый Бжозовский и Маккласки, алгоритм Макнотон и Ямада,^[1] и использование Лемма Ардена.

Описание алгоритма

Согласно Гроссу и Йеллен (2004),^[2] алгоритм можно проследить до Клини (1956).^[3] Представление алгоритма в случае детерминированные конечные автоматы (DFA) даны в Hopcroft and Ullman (1979).^[4] Представление алгоритма для NFA ниже следует Gross and Yellen (2004).^[2]

Учитывая недетерминированный конечный автомат M = (Q, Σ, δ, q₀, F), с Q = { q₀,...,q_п } свой набор состояния, алгоритм вычисляет

наборы р^k
_ij всех струн, которые занимают M от государства q_я к q_j без прохождения состояний с номерами выше, чем k.

Здесь «пройти через состояние» означает войти и оставив это, так что оба я и j может быть выше чем k, но никакое промежуточное состояние не может. р^k
_ij представлен регулярным выражением; алгоритм вычисляет их шаг за шагом для k = -1, 0, ..., п. Так как нет штата с номером выше, чем п, регулярное выражение р^п
_0j представляет собой набор всех строк, которые принимают M из его начальное состояние q₀ к q_j. Если F = { q₁,...,q_ж } - это набор принять состояния, то регулярное выражение р^п
₀₁ | ... | р^п
_0f представляет язык принято к M.

Исходные регулярные выражения для k = -1, вычисляются для я≠j:

р⁻¹
_ij = а₁ | ... | а_м куда q_j ∈ δ (q_я,а₁), ..., q_j ∈ δ (q_я,а_м)

и следующим образом для я=j:

р⁻¹
_ii = а₁ | ... | а_м | ε где q_я ∈ δ (q_я,а₁), ..., q_я ∈ δ (q_я,а_м)

Другими словами, р⁻¹
_ij упоминает все буквы, обозначающие переход от я к j, и мы также включаем ε в случае, когда я=j.

После этого на каждом шаге выражения р^k
_ij вычисляются из предыдущих

р^k
_ij = р^k-1
_ik (р^k-1
_кк)^* р^k-1
_кДж | р^k-1
_ij

Другой способ понять работу алгоритма - это «метод исключения», где состояния от 0 до п удаляются последовательно: когда состояние k удаляется, регулярное выражение р^k-1
_ij, который описывает слова, обозначающие путь из состояния я>k заявить j>k, переписывается в р^k
_ij чтобы учесть возможность перехода через «исключенное» состояние k.

Индукцией по k, можно показать, что длина^[5] каждого выражения р^k
_ij самое большее 1/3(4^k+1(6s+7) - 4) символы, где s обозначает количество символов в Σ. Следовательно, длина регулярного выражения, представляющего язык, принятый M самое большее 1/3(4^п+1(6s+7)ж - ж - 3) символы, где ж обозначает количество конечных состояний. Это экспоненциальное разрушение неизбежно, поскольку существуют семейства DFA, для которых любое эквивалентное регулярное выражение должно иметь экспоненциальный размер.^[6]

На практике размер регулярного выражения, полученного при запуске алгоритма, может сильно отличаться в зависимости от порядка, в котором состояния рассматриваются процедурой, т. Е. Порядка, в котором они пронумерованы от 0 до п.

Пример

Пример DFA для алгоритма Клини

Представленный на картинке автомат можно описать как M = (Q, Σ, δ, q₀, F) с

• набор состояний Q = { q₀, q₁, q₂ },
• входной алфавит Σ = { а, б },
• переходная функция δ с δ (q₀,а)=q₀, δ (q₀,б)=q₁, δ (q₁,а)=q₂, δ (q₁,б)=q₁, δ (q₂,а)=q₁, а δ (q₂,б)=q₁,
• начальное состояние q₀, и
• набор состояний принятия F = { q₁ }.

Алгоритм Клини вычисляет исходные регулярные выражения как

р^−1 00	= а | ε
р^−1 01	= б
р^−1 02	= ∅
р^−1 10	= ∅
р^−1 11	= б | ε
р^−1 12	= а
р^−1 20	= ∅
р^−1 21	= а | б
р^−1 22	= ε

После этого р^k
_ij вычисляются из р^k-1
_ij шаг за шагом для k = 0, 1, 2.Клини алгебра равенства используются для максимального упрощения регулярных выражений.

Шаг 0

р^0 00	= р^−1 00 (р^−1 00)^* р^−1 00 | р^−1 00	= (а | ε)	(а | ε)^*	(а | ε)	| а | ε	= а^*
р^0 01	= р^−1 00 (р^−1 00)^* р^−1 01 | р^−1 01	= (а | ε)	(а | ε)^*	б	| б	= а^* б
р^0 02	= р^−1 00 (р^−1 00)^* р^−1 02 | р^−1 02	= (а | ε)	(а | ε)^*	∅	| ∅	= ∅
р^0 10	= р^−1 10 (р^−1 00)^* р^−1 00 | р^−1 10	= ∅	(а | ε)^*	(а | ε)	| ∅	= ∅
р^0 11	= р^−1 10 (р^−1 00)^* р^−1 01 | р^−1 11	= ∅	(а | ε)^*	б	| б | ε	= б | ε
р^0 12	= р^−1 10 (р^−1 00)^* р^−1 02 | р^−1 12	= ∅	(а | ε)^*	∅	| а	= а
р^0 20	= р^−1 20 (р^−1 00)^* р^−1 00 | р^−1 20	= ∅	(а | ε)^*	(а | ε)	| ∅	= ∅
р^0 21	= р^−1 20 (р^−1 00)^* р^−1 01 | р^−1 21	= ∅	(а | ε)^*	б	| а | б	= а | б
р^0 22	= р^−1 20 (р^−1 00)^* р^−1 02 | р^−1 22	= ∅	(а | ε)^*	∅	| ε	= ε

Шаг 1

р^1 00	= р^0 01 (р^0 11)^* р^0 10 | р^0 00	= а^*б	(б | ε)^*	∅	| а^*	= а^*
р^1 01	= р^0 01 (р^0 11)^* р^0 11 | р^0 01	= а^*б	(б | ε)^*	(б | ε)	| а^* б	= а^* б^* б
р^1 02	= р^0 01 (р^0 11)^* р^0 12 | р^0 02	= а^*б	(б | ε)^*	а	| ∅	= а^* б^* ба
р^1 10	= р^0 11 (р^0 11)^* р^0 10 | р^0 10	= (б | ε)	(б | ε)^*	∅	| ∅	= ∅
р^1 11	= р^0 11 (р^0 11)^* р^0 11 | р^0 11	= (б | ε)	(б | ε)^*	(б | ε)	| б | ε	= б^*
р^1 12	= р^0 11 (р^0 11)^* р^0 12 | р^0 12	= (б | ε)	(б | ε)^*	а	| а	= б^* а
р^1 20	= р^0 21 (р^0 11)^* р^0 10 | р^0 20	= (а | б)	(б | ε)^*	∅	| ∅	= ∅
р^1 21	= р^0 21 (р^0 11)^* р^0 11 | р^0 21	= (а | б)	(б | ε)^*	(б | ε)	| а | б	= (а | б) б^*
р^1 22	= р^0 21 (р^0 11)^* р^0 12 | р^0 22	= (а | б)	(б | ε)^*	а	| ε	= (а | б) б^* а | ε

Шаг 2

р^2 00	= р^1 02 (р^1 22)^* р^1 20 | р^1 00	= а^*б^*ба	((а|б)б^*а | ε)^*	∅	| а^*	= а^*
р^2 01	= р^1 02 (р^1 22)^* р^1 21 | р^1 01	= а^*б^*ба	((а|б)б^*а | ε)^*	(а|б)б^*	| а^* б^* б	= а^* б (а (а | б) | б)^*
р^2 02	= р^1 02 (р^1 22)^* р^1 22 | р^1 02	= а^*б^*ба	((а|б)б^*а | ε)^*	((а|б)б^*а | ε)	| а^* б^* ба	= а^* б^* б (а (а | б) б^*)^* а
р^2 10	= р^1 12 (р^1 22)^* р^1 20 | р^1 10	= б^* а	((а|б)б^*а | ε)^*	∅	| ∅	= ∅
р^2 11	= р^1 12 (р^1 22)^* р^1 21 | р^1 11	= б^* а	((а|б)б^*а | ε)^*	(а|б)б^*	| б^*	= (а (а | б) | б)^*
р^2 12	= р^1 12 (р^1 22)^* р^1 22 | р^1 12	= б^* а	((а|б)б^*а | ε)^*	((а|б)б^*а | ε)	| б^* а	= (а (а | б) | б)^* а
р^2 20	= р^1 22 (р^1 22)^* р^1 20 | р^1 20	= ((а|б)б^*а | ε)	((а|б)б^*а | ε)^*	∅	| ∅	= ∅
р^2 21	= р^1 22 (р^1 22)^* р^1 21 | р^1 21	= ((а|б)б^*а | ε)	((а|б)б^*а | ε)^*	(а|б)б^*	| (а | б) б^*	= (а | б) (а (а | б) | б)^*
р^2 22	= р^1 22 (р^1 22)^* р^1 22 | р^1 22	= ((а|б)б^*а | ε)	((а|б)б^*а | ε)^*	((а|б)б^*а | ε)	| (а | б) б^* а | ε	= ((а | б) б^* а)^*

С q₀ это начальное состояние и q₁ единственное состояние приема, регулярное выражение р²
₀₁ обозначает набор всех строк, принимаемых автоматом.

Смотрите также

• Алгоритм Флойда-Уоршолла - алгоритм на взвешенных графах, который может быть реализован алгоритмом Клини с использованием определенного Клини алгебра
• Проблема высоты звезды - какова минимальная глубина вложения звездочек для всех регулярных выражений, соответствующих данному DFA?
• Обобщенная проблема высоты звезды - если в регулярных выражениях дополнительно разрешен оператор дополнения, может ли глубина вложения звезд выход алгоритма Клини ограничен фиксированной границей?
• Алгоритм построения Томпсона - преобразует регулярное выражение в конечный автомат

Рекомендации

1. McNaughton, R .; Ямада, Х. (март 1960). "Регулярные выражения и графы состояний для автоматов". Операции IRE на электронных компьютерах. ИС-9 (1): 39–47. Дои:10.1109 / TEC.1960.5221603. ISSN  0367-9950.
2. Джонатан Л. Гросс и Джей Йеллен, изд. (2004). Справочник по теории графов. Дискретная математика и ее приложения. CRC Press. ISBN  1-58488-090-2. Здесь: раздел 2.1, замечание R13 на стр.65
3. Клини, Стивен С. (1956). «Представление событий в нервных сетях и конечном автомате» (PDF). Исследования автоматов, Annals of Math. Исследования. Princeton Univ. Нажмите. 34. Здесь: раздел 9, стр.37-40
4. Джон Э. Хопкрофт, Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. ISBN  0-201-02988-X. Здесь: Раздел 3.2.1, страницы 91-96
5. Точнее, количество символов регулярного выражения "а_я"," ε "," | ","^*«,« · »; Не считая скобок.
6. Грубер, Германн; Хольцер, Маркус (2008). Ацето, Лука; Дамгард, Иван; Голдберг, Лесли Энн; Halldórsson, Magnús M .; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.). "Конечные автоматы, связность диграфов и размер регулярных выражений". Автоматы, языки и программирование. Конспект лекций по информатике. Springer Berlin Heidelberg. 5126: 39–50. Дои:10.1007/978-3-540-70583-3_4. ISBN  9783540705833.. Теорема 16.