Алгоритм Клинса - Википедия - Kleenes algorithm

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

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

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

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

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

Здесь «пройти через состояние» означает войти и оставив это, так что оба я и j может быть выше чем k, но никакое промежуточное состояние не может. рk
ij
представлен регулярным выражением; алгоритм вычисляет их шаг за шагом для k = -1, 0, ..., п. Так как нет штата с номером выше, чем п, регулярное выражение рп
0j
представляет собой набор всех строк, которые принимают M из его начальное состояние q0 к qj. Если F = { q1,...,qж } - это набор принять состояния, то регулярное выражение рп
01
| ... | рп
0f
представляет язык принято к M.

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

р−1
ij
= а1 | ... | ам куда qj ∈ δ (qя,а1), ..., qj ∈ δ (qя,ам)

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

р−1
ii
= а1 | ... | ам | ε где qя ∈ δ (qя,а1), ..., qя ∈ δ (qя,ам)

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

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

Пример

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

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

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

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

р−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
= ((а|б)б*а | ε)((а|б)б*а | ε)*((а|б)б*а | ε)| (а | б) б* а | ε= ((а | б) б* а)*

С q0 это начальное состояние и q1 единственное состояние приема, регулярное выражение р2
01
обозначает набор всех строк, принимаемых автоматом.

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

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

  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.