Теория автоматов. - 9 стр.

графовые представления, а запись в виде так называемых продукций или грам-
матических правил, представленных в двух столбцах соответственно:

      A → aB                               A:: = aB / bB / aC
      A → bb                               B:: = bC / b
      A → aC                               C:: = a
      B → bC
      B→b
      C→a

Такого рода грамматики называют регулярными, или автоматными.
      Автоматы такого типа будут рассмотрены в связи с изучением теории
формальных языков и грамматик.



                                  УПРАЖНЕНИЯ

       Звездочками отмечены задания, для которых приводятся решения.
       1.Построить (синтезировать) автомат по содержательному описанию.
       1.1.∗ На вход автомата могут поступать сигналы R, S и T. На входной
сигнал R автомат выдает выходной сигнал 0, на S- выходной сигнал 1 и на T-
выходной сигнал, противоположный предыдущему выходному сигналу. Для
определенности считаем, что в начальном состоянии автомат помнит
’’предыдущий’’ выходной сигнал 0 .
       1.2.∗ Автомат имеет две входные шины X1 и X2 , на которые в дискретные
моменты независимо друг от друга могут поступать сигналы 0 или 1. В автома-
те вычисляется функция f=x1 ⊕ x2, а затем определяется, сколько раз с учетом
данного момента времени функция f принимала значение 1. Выходной сигнал Y
может иметь три значения:
       Y = 0,если f = 0;
       Y = 1,если f = 1 и суммарное число случаев, включая данный, когда f
              равнялась единице, нечетно;
       Y = 2 в остальных случаях.
       1.3.∗Автомат управляет светофором на перекрестке дорог ”вертикальная
- горизонтальная”. Считается, что при открытом светофоре (зеленом свете) ма-
шины преодолевают перекресток мгновенно. Светофор переключается (мгно-
венно), если число ожидающих машин с обеих сторон перпендикулярной улицы
достигло трех.
       1.4.∗ На вход автомата могут поступать символы, допустимые в языке
ПЛ/1. Автомат выдает сигнал U, если на вход поступил идентификатор, в про-
тивном случае выдает сигнал Н. Считаем, что идентификатор впереди и сзади
ограничен пробелами.
       1.6.∗ Автомат Мура, принимая на входе монеты 10; 15 и 20 коп., выдает
сигнал П, если значение текущей суммы опущенных монет кратно 50 и не крат-
но 1 руб.; выдает сигнал Р, если сумма кратна 1 руб.; во всех остальных случаях
выдает сигнал 0.
       1.20* На вход автомата по двум шинам x1 и x2 поступают различные
комбинации из нулей и единиц, воспринимаемые как двоичные числа. Автомат