Специальная математика. Соловьев А.Е. - 76 стр.

.
Распознающий автомат – это, как правило, недетерминированный частичный автомат.
То есть по одному и тому же сигналу можно перейти в различные состояния, а в некоторых
состояниях нет перехода для ряда входных сигналов.


                            B
                   a,b                   b

               A            b                      F

                        a                 a
                                C

   0      0     0 1
   A      B     C F
a B,C           F
b B       С,F
Кстати, строка, приписывающая состояниям выходные сигналы совсем не обязательна.

Представление этого автомата с помощью автоматной грамматики:
A  aB | bB | aC
B  bC | b
Ca
Это праворекурсивная автоматная грамматика.


                                         7.5. Понятие транслятора

  Транслятор - программа или устройство, переводящее входную строку а языка А во
выходную строку b языка B с сохранением смысла.
Это нестрогое определение, поскольку «сохранение смысла» можно понимать весьма
различно.


    аА                     bB
                        Т


Для того, чтобы облегчить переход от входного языка к выходному, а также с целью
упростить оптимизацию, процесс трансляции часто разбивают на этапы, с трансляцией на
промежуточные языки. Такие трансляторы называются многопроходными.


а = a0             а1               а2                 а3              аn = b
          T1                T2                T3            ...   Tn


По типу трансляции трансляторы подразделяются на компиляторы и интерпретаторы.
Компиляторы осуществляет перевод всего текста до начала выполнения (вычисления).


                                                        — 76 —