В теоретической информатике , в частности в теории формального языка , алгоритм Клини преобразует данный недетерминированный конечный автомат (NFA) в регулярное выражение . Вместе с другими алгоритмами преобразования он устанавливает эквивалентность нескольких форматов описания для обычных языков . Альтернативные представления одного и того же метода включают «метод исключения» приписываемую Бжозовского и Маккласки , алгоритм Макнотоном и Ямада , [1] и использование леммы Арден .
Описание алгоритма
Согласно Гроссу и Йеллен (2004), [2] алгоритм восходит к Клини (1956). [3] Описание алгоритма в случае детерминированных конечных автоматов (ДКА) дано в Hopcroft and Ullman (1979). [4] Алгоритм для NFA представлен ниже в соответствии с Gross and Yellen (2004). [2]
Для недетерминированного конечного автомата M = ( Q , Σ, δ, q 0 , F ) с набором состояний Q = { q 0 , ..., q n } алгоритм вычисляет
- множества Rk
ijвсех строк, которые переводят M из состояния q i в q j, не проходя через какое-либо состояние с номером выше k .
Здесь «прохождение состояния» означает вход в него и выход из него, поэтому и i, и j могут быть выше k , но никакое промежуточное состояние не может. Каждый набор Rk
ijпредставлен регулярным выражением; алгоритм вычисляет их шаг за шагом для k = -1, 0, ..., n . Поскольку нет состояний с номерами выше n , регулярное выражение Rп
0jпредставляет набор всех строк, которые переводят M из начального состояния q 0 в q j . Если F = { q 1 , ..., q f } - набор состояний принятия , регулярное выражение Rп
01| ... | рп
0fпредставляет собой язык , принятый на M .
Исходные регулярные выражения для k = -1 вычисляются для i ≠ j следующим образом :
- р−1
ij= a 1 | ... | a m, где q j ∈ δ ( q i , a 1 ), ..., q j ∈ δ ( q i , a m )
и следующим образом для i = j :
- р−1
ii= a 1 | ... | а м | ε, где q i ∈ δ ( q i , a 1 ), ..., q i ∈ δ ( q i , a m )
Другими словами, R−1
ijупоминает все буквы, обозначающие переход от i к j , и мы также включаем ε в случае, когда i = j .
После этого на каждом шаге выражения Rk
ij вычисляются из предыдущих
- рk
ij= Rk -1
ik( Rк -1
кк) * Rк -1
кДж| рk -1
ij
Другой способ понять работу алгоритма - это «метод исключения», при котором последовательно удаляются состояния от 0 до n : при удалении состояния k регулярное выражение Rk -1
ij, который описывает слова, обозначающие путь от состояния i > k к состоянию j > k , переписывается в Rk
ijчтобы учесть возможность перехода через «исключенное» состояние k .
Индукцией по k можно показать, что длина [5] каждого выражения Rk
ij самое большее 1/3(4 k +1 (6 s +7) - 4) символов, где s обозначает количество символов в Σ. Следовательно, длина регулярного выражения, представляющего язык, принятый M , не превышает 1/3(4 n +1 (6 s +7) f - f - 3) символов, где f обозначает количество конечных состояний. Этот экспоненциальный взрыв неизбежен, потому что существуют семейства DFA, для которых любое эквивалентное регулярное выражение должно иметь экспоненциальный размер. [6]
На практике размер регулярного выражения, полученного при запуске алгоритма, может сильно отличаться в зависимости от порядка, в котором состояния рассматриваются процедурой, т. Е. Порядка, в котором они пронумерованы от 0 до n .
Пример
Автомат, изображенный на рисунке, можно описать как M = ( Q , Σ, δ, q 0 , F ) с
- множество состояний Q = { q 0 , q 1 , q 2 },
- входной алфавит Σ = { a , b },
- функция перехода δ с δ ( q 0 , a ) = q 0 , δ ( q 0 , b ) = q 1 , δ ( q 1 , a ) = q 2 , δ ( q 1 , b ) = q 1 , δ ( q 2 , a ) = q 1 и δ ( q 2 , b ) = q 1 ,
- начальное состояние q 0 , и
- набор состояний приема F = { q 1 }.
Алгоритм Клини вычисляет исходные регулярные выражения как
р−1
00= а | ε р−1
01= b р−1
02= ∅ р−1
10= ∅ р−1
11= b | ε р−1
12= а р−1
20= ∅ р−1
21= а | б р−1
22= ε
После этого Rk
ijвычисляются из Rk -1
ijшаг за шагом для k = 0, 1, 2. Равенства алгебры Клини используются для максимального упрощения регулярных выражений.
- Шаг 0
р0
00= R−1
00( R−1
00) * R−1
00| р−1
00= ( а | ε) ( а | е) * ( а | е) | а | ε = а * р0
01= R−1
00( R−1
00) * R−1
01| р−1
01= ( а | ε) ( а | е) * б | б = а * б р0
02= R−1
00( R−1
00) * R−1
02| р−1
02= ( а | ε) ( а | е) * ∅ | ∅ = ∅ р0
10= R−1
10( R−1
00) * R−1
00| р−1
10= ∅ ( а | е) * ( а | е) | ∅ = ∅ р0
11= R−1
10( R−1
00) * R−1
01| р−1
11= ∅ ( а | е) * б | б | ε = b | ε р0
12= R−1
10( R−1
00) * R−1
02| р−1
12= ∅ ( а | е) * ∅ | а = а р0
20= R−1
20( R−1
00) * R−1
00| р−1
20= ∅ ( а | е) * ( а | е) | ∅ = ∅ р0
21= R−1
20( R−1
00) * R−1
01| р−1
21= ∅ ( а | е) * б | а | б = а | б р0
22= R−1
20( R−1
00) * R−1
02| р−1
22= ∅ ( а | е) * ∅ | ε = ε
- Шаг 1
р1
00= R0
01( R0
11) * R0
10| р0
00= а * б ( b | ε) * ∅ | а * = а * р1
01= R0
01( R0
11) * R0
11| р0
01= а * б ( b | ε) * ( b | ε) | а * б = а * б * б р1
02= R0
01( R0
11) * R0
12| р0
02= а * б ( b | ε) * а | ∅ = а * б * ба р1
10= R0
11( R0
11) * R0
10| р0
10= ( b | ε) ( b | ε) * ∅ | ∅ = ∅ р1
11= R0
11( R0
11) * R0
11| р0
11= ( b | ε) ( b | ε) * ( b | ε) | б | ε = Ь * р1
12= R0
11( R0
11) * R0
12| р0
12= ( b | ε) ( b | ε) * а | а = б * а р1
20= R0
21( R0
11) * R0
10| р0
20= ( а | б ) ( b | ε) * ∅ | ∅ = ∅ р1
21= R0
21( R0
11) * R0
11| р0
21= ( а | б ) ( b | ε) * ( b | ε) | а | б = ( а | Ь ) Ь * р1
22= R0
21( R0
11) * R0
12| р0
22= ( а | б ) ( b | ε) * а | ε = ( a | b ) b * a | ε
- Шаг 2
р2
00= R1
02( R1
22) * R1
20| р1
00= а * б * ба (( a | b ) b * a | ε) * ∅ | а * = а * р2
01= R1
02( R1
22) * R1
21| р1
01= а * б * ба (( a | b ) b * a | ε) * ( а | б ) б * | а * б * б = a * b ( a ( a | b ) | b ) * р2
02= R1
02( R1
22) * R1
22| р1
02= а * б * ба (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | а * б * ба = a * b * b ( a ( a | b ) b * ) * a р2
10= R1
12( R1
22) * R1
20| р1
10= б * а (( a | b ) b * a | ε) * ∅ | ∅ = ∅ р2
11= R1
12( R1
22) * R1
21| р1
11= б * а (( a | b ) b * a | ε) * ( а | б ) б * | б * = ( а ( а | б ) | б ) * р2
12= R1
12( R1
22) * R1
22| р1
12= б * а (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | б * а = ( а ( а | б ) | б ) * а р2
20= R1
22( R1
22) * R1
20| р1
20= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ∅ | ∅ = ∅ р2
21= R1
22( R1
22) * R1
21| р1
21= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ( а | б ) б * | ( а | б ) б * = ( a | b ) ( a ( a | b ) | b ) * р2
22= R1
22( R1
22) * R1
22| р1
22= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | ( a | b ) b * a | ε = (( a | b ) b * a ) *
Поскольку q 0 - начальное состояние, а q 1 - единственное принимаемое состояние, регулярное выражение R2
01 обозначает набор всех строк, принимаемых автоматом.
Смотрите также
- Алгоритм Флойда – Уоршалла - алгоритм на взвешенных графах, который может быть реализован алгоритмом Клини с использованием определенной алгебры Клини.
- Проблема высоты звезды - какова минимальная глубина вложенности звезд для всех регулярных выражений, соответствующих заданному DFA?
- Обобщенная проблема высоты звезды - если в регулярных выражениях дополнительно разрешен оператор дополнения, можно ли ограничить глубину вложенности звезд в выходных данных алгоритма Клини фиксированной границей?
- Алгоритм построения Томпсона - преобразует регулярное выражение в конечный автомат
Рекомендации
- ^ McNaughton, R .; Ямада, Х. (март 1960). "Регулярные выражения и графы состояний для автоматов". Операции IRE на электронных компьютерах . ИС-9 (1): 39–47. DOI : 10.1109 / TEC.1960.5221603 . ISSN 0367-9950 .
- ^ а б Джонатан Л. Гросс и Джей Йеллен, изд. (2004). Справочник по теории графов . Дискретная математика и ее приложения. CRC Press. ISBN 1-58488-090-2. Здесь: раздел 2.1, замечание R13 на стр.65
- ^ Клини, Стивен С. (1956). «Представление событий в нервных сетях и конечном автомате» (PDF) . Исследования автоматов, Annals of Math. Исследования . Princeton Univ. Нажмите. 34 . Здесь: раздел 9, с.37-40
- ^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 0-201-02988-X. Здесь: Раздел 3.2.1, страницы 91-96
- ^ Точнее, количество символов регулярного выражения, « a i », «ε», «|», « * », «·»; не считая скобок.
- ^ Грубер, Германн; Хольцер, Маркус (2008). Ацето, Лука; Дамгард, Иван; Голдберг, Лесли Энн; Halldórsson, Magnús M .; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.). «Конечные автоматы, связность орграфов и размер регулярных выражений» . Автоматы, языки и программирование . Конспект лекций по информатике. Springer Berlin Heidelberg. 5126 : 39–50. DOI : 10.1007 / 978-3-540-70583-3_4 . ISBN 9783540705833.. Теорема 16.