Основы трансляции - 11 стр.

UptoLike

ВУЗ: 

ВПИ ВолгГТУ | Волжский

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

Рубрика: 

11
где
A
1
! A
2
j A
2
A
0
1
A
0
1
! +A
2
j ¡A
2
j +A
2
A
0
1
j ¡A
2
A
0
1
A
2
! A
3
j A
3
A
0
2
A
0
2
! ¤A
3
j =A
3
j ¤A
3
A
0
2
j =A
3
A
0
2
A
3
! (A
1
) j a j b
1.6. Алгоритм построения детерминированного конечного автомата
Конечный автомат (КА) часто представляют в виде диаграммы или графа
переходов автомата.
Определение: Граф переходов КА – это направленный граф, вершины
которого помечены символами состояний КА, и в котором есть дуга ,
, помеченная символом , если в КА определена и
. Начальное и конечное состояния автомата на графе состояний
помечаются специальным образом: начальное состояние – дополнительной
пунктирной линией, конечное состояние – дополнительной сплошной линией.
Рассмотрим конечный автомат:
,
где , , , , .
На рис. 1 приведен пример графа состояний этого конечного автомата.
Рис 1. Граф переходов конечного автомата
Определение: Конечный автомат
M (Q; V; ±; q
0
; F)
называют
детерминированным конечным автоматом (ДКА), если в каждом из его
состояний для любого входного символа функция перехода содержит не более
одного состояния
8a 2 V
,
: либо
± (q; a) = frg
, где
r 2 Q
, либо
± (q; a) = ?
. В противном случае конечный автомат называют
недетерминированным.
ДКА может быть задан в виде пятерки:
M (Q; V; ±; q
0
; F)
, где
Q
- конечное
множество состояний автомата,
Q 6= ?
;
V
- конечное множество допустимых
входных символов,
V 6= ?
;
±
- функция переходов, отображающая
V
¤
£ Q
в
множество : , , ; - начальное состояние конечного
автомата, ; - множество конечных состояний автомата, , .
Если функция переходов ДКА определена для каждого состояния автомата,
то автомат называется полностью определенным ДКА: , :
, .
Доказано, что для любого КА можно построить эквивалентный ему ДКА.
Моделировать работу ДКА существенно проще, чем работу произвольного КА, 
  где     A1 ! A2 j A2A01
          A01 ! +A2 j ¡A2 j +A2A01 j ¡A2A01
          A2 ! A3 j A3A02
          A02 ! ¤A3 j =A3 j ¤A3A02 j =A3A02
          A3 ! (A1) j a j b

   1.6. Алгоритм построения детерминированного конечного автомата
   Конечный автомат (КА) часто представляют в виде диаграммы или графа
переходов автомата.
   Определение: Граф переходов КА – это направленный граф, вершины
которого помечены символами состояний КА, и в котором есть дуга          ,
         , помеченная символом           , если в КА определена         и
          . Начальное и конечное состояния автомата на графе состояний
помечаются специальным образом: начальное состояние – дополнительной
пунктирной линией, конечное состояние – дополнительной сплошной линией.
   Рассмотрим конечный автомат:
                                                         ,
   где            ,            ,           ,           ,           .
   На рис. 1 приведен пример графа состояний этого конечного автомата.




                    Рис 1. Граф переходов конечного автомата
   Определение:     Конечный     автомат      M (Q; V; ±; q0; F)    называют
детерминированным конечным автоматом (ДКА), если в каждом из его
состояний для любого входного символа функция перехода содержит не более
одного состояния 8a 2 V , 8q 2 Q: либо ± (q; a) = frg, где r 2 Q, либо
± (q; a) = ?.  В    противном   случае    конечный      автомат     называют
недетерминированным.
   ДКА может быть задан в виде пятерки: M (Q; V; ±; q0; F), где Q - конечное
множество состояний автомата, Q 6= ?; V - конечное множество допустимых
входных символов, V 6= ?; ± - функция переходов, отображающая V ¤ £ Q в
множество :             ,     ,        ;   - начальное состояние конечного
автомата,       ; - множество конечных состояний автомата,           ,     .
   Если функция переходов ДКА определена для каждого состояния автомата,
то автомат называется полностью определенным ДКА:                  ,         :
             ,    .
   Доказано, что для любого КА можно построить эквивалентный ему ДКА.
Моделировать работу ДКА существенно проще, чем работу произвольного КА,
                                   11

Страницы