Алгоритм Клини - Kleene's algorithm
В теоретической информатике , в частности в теории формального языка , алгоритм Клини преобразует данный недетерминированный конечный автомат (NFA) в регулярное выражение . Вместе с другими алгоритмами преобразования он устанавливает эквивалентность нескольких форматов описания для обычных языков . Альтернативные представления того же метода включают «метод исключения», приписываемый Бжозовскому и МакКласки , алгоритм Макнотона и Ямады и использование леммы Ардена .
Описание алгоритма
Согласно Гроссу и Йеллен (2004), алгоритм восходит к Клини (1956). Описание алгоритма в случае детерминированных конечных автоматов (ДКА) дано в работе Хопкрофта и Ульмана (1979). Представление алгоритма для NFA ниже следует Gross and Yellen (2004).
Для недетерминированного конечного автомата M = ( Q , Σ, δ, q 0 , F ) с набором состояний Q = { q 0 , ..., q n } алгоритм вычисляет
- множества R k
ij всех строк, которые переводят M из состояния q i в q j, не проходя через какое-либо состояние с номером выше k .
Здесь «прохождение состояния» означает вход в него и выход из него, поэтому и i, и j могут быть выше k , но никакое промежуточное состояние не может. Каждый набор R k
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 .
После этого на каждом шаге выражения R k
ij вычисляются из предыдущих
-
р k
ij = R k -1
ik ( R к -1
кк ) * R к -1
кДж | р k -1
ij
Другой способ понять работу алгоритма - это «метод исключения», при котором последовательно удаляются состояния от 0 до n : при удалении состояния k регулярное выражение R k -1
ij , который описывает слова, обозначающие путь от состояния i > k к состоянию j > k , переписывается в R k
ij чтобы учесть возможность перехода через «исключенное» состояние k .
Индукцией по k можно показать, что длина каждого выражения R k
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, для которых любое эквивалентное регулярное выражение должно иметь экспоненциальный размер.
На практике размер регулярного выражения, полученного при запуске алгоритма, может сильно отличаться в зависимости от порядка, в котором состояния рассматриваются процедурой, т. Е. Порядка, в котором они пронумерованы от 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= ε
После этого R k
ij вычисляются из R k -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= R 0
01 ( R 0
11 ) * R 0
10 | р 0
00= а * б ( b | ε) * ∅ | а * = а * р 1
01= R 0
01 ( R 0
11 ) * R 0
11 | р 0
01= а * б ( b | ε) * ( b | ε) | а * б = а * б * б р 1
02= R 0
01 ( R 0
11 ) * R 0
12 | р 0
02= а * б ( b | ε) * а | ∅ = а * б * ба р 1
10= R 0
11 ( R 0
11 ) * R 0
10 | р 0
10= ( Ь | ε) ( b | ε) * ∅ | ∅ = ∅ р 1
11= R 0
11 ( R 0
11 ) * R 0
11 | р 0
11= ( Ь | ε) ( b | ε) * ( b | ε) | б | ε = Ь * р 1
12= R 0
11 ( R 0
11 ) * R 0
12 | р 0
12= ( Ь | ε) ( b | ε) * а | а = б * а р 1
20= R 0
21 ( R 0
11 ) * R 0
10 | р 0
20= ( а | б ) ( b | ε) * ∅ | ∅ = ∅ р 1
21= R 0
21 ( R 0
11 ) * R 0
11 | р 0
21= ( а | б ) ( b | ε) * ( b | ε) | а | б = ( а | б ) Ь * р 1
22= R 0
21 ( R 0
11 ) * R 0
12 | р 0
22= ( а | б ) ( b | ε) * а | ε = ( a | b ) b * a | ε
- Шаг 2
р 2
00= R 1
02 ( R 1
22 ) * R 1
20 | р 1
00= а * б * ба (( a | b ) b * a | ε) * ∅ | а * = а * р 2
01= R 1
02 ( R 1
22 ) * R 1
21 | р 1
01= а * б * ба (( a | b ) b * a | ε) * ( а | б ) б * | а * б * б = a * b ( a ( a | b ) | b ) * р 2
02= R 1
02 ( R 1
22 ) * R 1
22 | р 1
02= а * б * ба (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | а * б * ба = a * b * b ( a ( a | b ) b * ) * a р 2
10= R 1
12 ( R 1
22 ) * R 1
20 | р 1
10= б * а (( a | b ) b * a | ε) * ∅ | ∅ = ∅ р 2
11= R 1
12 ( R 1
22 ) * R 1
21 | р 1
11= б * а (( a | b ) b * a | ε) * ( а | б ) б * | б * = ( а ( а | б ) | б ) * р 2
12= R 1
12 ( R 1
22 ) * R 1
22 | р 1
12= б * а (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | б * а = ( а ( а | б ) | б ) * а р 2
20= R 1
22 ( R 1
22 ) * R 1
20 | р 1
20= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ∅ | ∅ = ∅ р 2
21= R 1
22 ( R 1
22 ) * R 1
21 | р 1
21= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ( а | б ) б * | ( а | б ) б * = ( a | b ) ( a ( a | b ) | b ) * р 2
22= R 1
22 ( R 1
22 ) * R 1
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 - единственное принимаемое состояние, регулярное выражение R 2
01 обозначает набор всех строк, принимаемых автоматом.
Смотрите также
- Алгоритм Флойда – Уоршалла - алгоритм на взвешенных графах, который может быть реализован алгоритмом Клини с использованием определенной алгебры Клини.
- Проблема высоты звезды - какова минимальная глубина вложенности звезд для всех регулярных выражений, соответствующих заданному DFA?
- Обобщенная проблема высоты звезды - если в регулярных выражениях дополнительно разрешен оператор дополнения, может ли глубина вложенности звезд в выходных данных алгоритма Клини быть ограничена фиксированной границей?
- Алгоритм построения Томпсона - преобразует регулярное выражение в конечный автомат