yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->      6.2 Автоматы-трансляторы с магазинной памятью

Дискретная математика

      6.2 Автоматы-трансляторы с магазинной памятью

 

     В ряде случаев при  обработке  регулярного  множества  кроме распознания необходимо его  преобразование  в  другое  множество.

Такие действия может выполнять МП-транслятор, на выходе  которого будет формироваться выходная цепочка.

     МП-транслятор задается :

     1.Конечным множеством входных символов (включая символ конца цепочки "-+").

     2.Конечным множеством выходных символов.

     3.Конечным множеством магазинных  символов  (включая  маркер дна магазина - \/).

     4.Конечным множеством состояний.

     5.Упpавляющей таблицей, котоpая каждой  комбинации:  входной символ, магазинный символ(верхний символ магазина),  состояние   ставит в соответствие действие  с  магазином,  входным  символом, состоянием и выходными символами.

     6.Hачальной конфигурацией (начальное состояние  и  начальное содеpжимое магазина).

     7.Множеством допускающих  конфигураций  (комбинаций  -  состояние МП-транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").

 

                                Строение ячейки в таблице переходов МП-траслятора  аналогичо ячейке МП-распознавателя, но добавляется еще четвертое поле, в

котором указываются выходные символы, выдаваемые на этом шаге  навыход.

                            --- Операции с магазином

                            ¦

                         ---+-----¬

                         ¦\ Вт.О /¦

           Состояния ----+ \Выт./П+--- Операции над входом

                         ¦Si\0 / Д¦

                         +---\/---+

                         ¦        ¦

                         L------T--

                                ¦

                                L- Выход (символы  на выходе)

     Ряд ячеек управляющей таблицы может без деления на поля  заолняться символом Е (состояние ошибки).  Если МП-транслятор  попал в такое состояние, то обработка цепочки прекращается и  такая

цепочка отвергается.

 

    Пример

     Распознать множество {W 2 V} и преобразовать его в множество

{1(n) 0(m)}, где W-цепочка из "0" и "1" ,V-цепочка обратная W,  m

- число "0" до "2", n - число "1" до "2".

     Конкретный пример  0010112110100 ==> 111000

                      Решение

     Опишем работу транслятора

     Для работы МП-транслятора необходимо  запоминать  не  только количество единиц и нулей цепочки W, но и их порядок для проверки цепочки V.  Это можно реализовать, вталкивая в магазин  символ  В при приходе единицы и символ А при приходе нуля до момента прихода двойки (т.е. до момента окончания цепочки W);таким  образом  в магазине окажется копия цепочки W, но записанная в  обратном  порядке (верхним в магазине  будет  символ,  пришедший  последним).

При этом на выход при поступлении "1" нужно выдать  тоже  "1",  а при поступлении "0" на выход не выдавать символов.  Приход двойки нужно зафиксировать сменой состояния транслятора.  Во втором состоянии действия транслятора следующие:

  а) верхний символ в магазине В и пришла единица - вытолкнуть В, на выход ничего не выдавать и перейти к обработке следующего символа входной цепочки;

б) верхний символ в магазине А и пришел ноль - вытолкнуть А, на выход выдать "0" и перейти к обработке следующего символа входной цепочки;

  в) оставшиеся два варианта - состояние ошибки Е (входная цепочка не соответствует виду {W 2 V}.

     Зададим МП-транслятор:

1. Управляющая таблица

                       є    0    і    1    і    2    і   Дґ    є

         г======T======+---------+---------+---------+---------¦

         ¦      ¦      ¦ \Вт. А /¦ \ Вт.В /¦         ¦         ¦

         ¦      ¦      ¦  \    / ¦  \    / ¦         ¦         ¦

         ¦      ¦  \/  ¦ S1\  / П¦ S1\  / П¦    Е    ¦  Отв.   ¦

         ¦      ¦      +----\/---+----\/---+         ¦         ¦

         ¦      ¦      ¦   ---   ¦     1   ¦         ¦         ¦

         ¦      +------+---------+---------+---------+---------¦

         ¦      ¦      ¦ \Вт. А /¦ \ Вт.В /¦ \  0   /¦         ¦

         ¦      ¦      ¦  \    / ¦  \    / ¦  \    / ¦         ¦

         ¦  S1  ¦  A   ¦ S1\  / П¦ S1\  / П¦ S2\  / П¦  Отв.   ¦

         ¦      ¦      +----\/---+----\/---+----\/---+         ¦

         ¦      ¦      ¦   ---   ¦    1    ¦    --   ¦         ¦

         ¦      +------+---------+---------+---------+---------¦

         ¦      ¦      ¦ \Вт. А /¦ \ Вт.В /¦ \      /¦         ¦

         ¦      ¦      ¦  \    / ¦  \    / ¦  \ 0  / ¦         ¦

         ¦      ¦  B   ¦ S1\  / П¦S1 \  / П¦ S2\  / П¦         ¦

         ¦      ¦      +----\/---+----\/---+----\/---+  Отв.   ¦

         ¦      ¦      ¦  ---    ¦     1   ¦   ---   ¦         ¦

         ¦------+------+---------+---------+---------+---------¦

         ¦      ¦  \/  ¦    Е    ¦    Е    ¦    Е    ¦  Доп.   ¦

         ¦      +------+---------+---------+---------+---------¦

         ¦      ¦      ¦ \Выт.А /¦         ¦         ¦         ¦

         ¦      ¦      ¦  \    / ¦    Е    ¦    Е    ¦         ¦

         ¦ S2   ¦  A   ¦ S2\  / П¦         ¦         ¦         ¦

         ¦      ¦      +----\/---+         ¦         ¦  Отв.   ¦

         ¦      ¦      ¦    0    ¦         ¦         ¦         ¦

         ¦      +------+---------+---------+---------+---------¦

         ¦      ¦      ¦         ¦ \ Выт.В/¦         ¦         ¦

         ¦      ¦      ¦         ¦  \    / ¦         ¦         ¦

         ¦      ¦  B   ¦    Е    ¦ S2\  / П¦    E    ¦         ¦

         ¦      ¦      ¦         +----\/---+         ¦  Отв.   ¦

         ¦      ¦      ¦         ¦   ---   ¦         ¦         ¦

         L======¦======¦=========¦=========¦=========¦=========-

                           - 10 -

2. Множество состояний {S1,S2}.

3. Множество входных символов :{0,1,2,-+};

4. Множество магазинных символов :{А,В,\/};

5. Множество выходных символов :{0,1};

 

 

Для примера разберем цепочку  0112110:

       г===========T=============T===========T=============¬

       ¦  Цепочка  ¦  Состояние  ¦ Магазин   ¦    Выход    ¦

       ¦-----------+-------------+-----------+-------------¦

       ¦ 0112110-+ ¦     S1      ¦      \/   ¦     ---     ¦

       ¦           ¦             ¦           ¦             ¦

       ¦  112110-+ ¦     S1      ¦    А \/   ¦     ---     ¦

       ¦           ¦             ¦           ¦             ¦

       ¦   12110-+ ¦      S1     ¦   ВА \/   ¦      1      ¦

       ¦           ¦             ¦           ¦             ¦

       ¦    2110-+ ¦      S1     ¦   ВВА\/   ¦     11      ¦

       ¦           ¦             ¦           ¦             ¦

       ¦     110-+ ¦      S2     ¦   ВВА\/   ¦     11      ¦

       ¦           ¦             ¦           ¦             ¦

       ¦      10-+ ¦      S2     ¦    ВА\/   ¦     11      ¦

       ¦           ¦             ¦           ¦             ¦

       ¦       0-+ ¦      S2     ¦     А\/   ¦     11      ¦

       ¦           ¦             ¦           ¦             ¦

       ¦        -+ ¦      S2     ¦      \/   ¦    110      ¦

       ¦           ¦             ¦           ¦             ¦

       L===========¦=============¦===========¦=============-

     Входная цепочка допущена и преобразована к заданному виду.

 

 

33