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

UptoLike

ВУЗ: 

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

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

Рубрика: 

12
поэтому произвольный КА стремятся преобразовать в ДКА. При построении
компиляторов чаще всего используют полностью определенный ДКА.
Алгоритм преобразования КА к детерминированному виду
Алгоритм преобразования произвольного КА в
эквивалентный ему ДКА заключается в следующем:
1. Множество состояний автомата строится из комбинаций всех
состояний множества автомата . Если , - состояния
автомата , , то всего будет состояний автомата .
Обозначим их так: , .
2. Функция переходов автомата строится так:
, где , так, что .
3. Обозначим .
4. Пусть , - конечные состояния автомата , ,
тогда множество конечных состояний автомата строится из всех
состояний, имеющих вид , .
Доказано, что описанный выше алгоритм строит ДКА, эквивалентный
заданному произвольному КА.
После построения из нового ДКА необходимо удалить все недостижимые
состояния.
Определение: Состояние КА называется
недостижимым, если ни при какой входной цепочке невозможен
переход автомата из начального состояния в состояние . Иначе состояние
называется достижимым.
Алгоритм удаления недостижимых состояний
Для работы алгоритма удаления недостижимых состояний используются два
множества: множество достижимых состояний и множество текущих
активных состояний на каждом шаге алгоритма . Результатом работы
алгоритма является полное множество достижимых состояний . Рассмотрим
работу алгоритма по шагам:
Шаг 1. ; ; .
Шаг 2. .
Шаг 3. , : .
Шаг 4. Если , то выполнение алгоритма закончено, иначе
, и перейти к шагу 3.
После выполнения данного алгоритма удаления недостижимых состояний из
КА можно исключить все состояния, не входящие в построенное множество .
Пример преобразования КА к детерминированному виду
Рассмотрим работу алгоритма преобразования произвольного КА в ДКА на
примере автомата
,
где , , . 
поэтому произвольный КА стремятся преобразовать в ДКА. При построении
компиляторов чаще всего используют полностью определенный ДКА.
           Алгоритм преобразования КА к детерминированному виду
   Алгоритм преобразования произвольного КА                                          в
эквивалентный ему ДКА                             заключается в следующем:
   1. Множество состояний            автомата          строится из комбинаций всех
состояний множества          автомата       . Если               ,        - состояния
автомата ,                        , то всего будет           состояний автомата       .
Обозначим их так:                 ,             .
   2.    Функция       переходов                автомата              строится    так:
                                     , где            ,          так, что            .
   3. Обозначим          .
   4. Пусть            ,       - конечные состояния автомата ,                        ,
тогда множество конечных состояний                  автомата        строится из всех
состояний, имеющих вид                ,       .
   Доказано, что описанный выше алгоритм строит ДКА, эквивалентный
заданному произвольному КА.
   После построения из нового ДКА необходимо удалить все недостижимые
состояния.
   Определение: Состояние                       КА                         называется
недостижимым, если ни при какой входной цепочке                           невозможен
переход автомата из начального состояния             в состояние . Иначе состояние
называется достижимым.
                Алгоритм удаления недостижимых состояний
   Для работы алгоритма удаления недостижимых состояний используются два
множества: множество достижимых состояний                     и множество текущих
активных состояний на каждом шаге алгоритма                    . Результатом работы
алгоритма является полное множество достижимых состояний . Рассмотрим
работу алгоритма по шагам:
   Шаг 1.          ;        ;             .
   Шаг 2.          .
   Шаг 3.        ,         :                          .
   Шаг 4. Если                     , то выполнение алгоритма закончено, иначе
              ,          и перейти к шагу 3.
   После выполнения данного алгоритма удаления недостижимых состояний из
КА можно исключить все состояния, не входящие в построенное множество .
   Пример преобразования КА к детерминированному виду
    Рассмотрим работу алгоритма преобразования произвольного КА в ДКА на
примере автомата
                                                               ,
   где               ,                 ,                   .

                                          12

Страницы