Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 39 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

41
Проиллюстрируем работу алгоритма на примере:
Пусть задан НКА M = ({H, A, B, S}, {0, 1}, δ, {H}, {S}), где:
δ(H, 1) = B δ(B, 0) = A
δ(A, 1) = B δ(A, 1) = S,
тогда соответствующий детерминированный конечный автомат будет та-
ким: K' = {[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB], [HAS],
[ABS], [HBS], [HABS]}
δ' ([A], 1) = [BS] δ' ([H], 1) = [B]
δ' ([B], 0) = [A] δ' ([HA], 1) = [BS]
δ' ([HB], 1) = [B] δ' ([HB], 0) = [A]
δ' ([HS], 1) = [B] δ' ([AB], 1) = [BS]
δ' ([AB], 0) = [A] δ' ([AS], 1) = [BS]
δ' ([BS], 0) = [A] δ' ([HAB], 0) = [A]
δ' ([HAB], 1) = [BS] δ' ([HAS], 1) = [BS]
δ' ([ABS], 1) = [BS] δ' ([ABS], 0) = [A]
δ' ([HBS], 1) = [B] δ' ([HBS], 0) = [A]
δ' ([HABS], 1) = [BS] δ' ([HABS], 0) = [A]
S' = {[S], [HS], [AS], [BS], [HAS], [ABS], [HBS], [HABS]}
Достижимыми состояниями в получившемся КА являются [H], [B], [A] и
[BS], поэтому остальные состояния удаляются.
Таким образом, M' = ({[H], [B], [A], [BS]}, {0, 1}, δ', H, {[BS]}), где
δ' ([A], 1) = [BS] δ' ([H], 1) = [B]
δ' ([B], 0) = [A] δ' ([BS], 0) = [A]
На рисунке изображены диаграммы состояний для НКА M (слева) и де-
терминированного КА M' (справа).
0
1
1
1
A
S
B
H
0
1
0
1
A
BS
B
H
Минимизация конечных автоматов
По конечному автомату часто можно построить автомат с меньшим чис-
лом состояний, эквивалентный исходному. Соответствующий процесс называ-
ется минимизацией конечного автомата. Вначале выбросим из автомата все со-
стояния, недостижимые из начального. Затем разобьем все состояния КА на
классы эквивалентности следующим способом: в первый класс отнесем все ко-
нечные состояния, а во второй – все остальные. Назовем эти состояния
0-эквивалентными. Теперь построим новое 1-эквивалентное разбиение, выде-
лив те состояния, которые по одинаковым символам переходят в 0-
эквивалентные состояния. Последовательно строя n+1-эквивалентные состоя-

Страницы