Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 24 стр.

                           T2:            0             q211L           q2z0R
                                          1             q211L           q200L
      а) D = 111100111011;                        б) D = 11010111.

   6.2. Машины Т1 и Т2 заданы таблицами соответствия:
                                                q10             q11             q12
                   T1:              0           q110R           q120R           q1z1L
                                    1           q101R           q101R

                                                q20             q21             q22
                   T2:              0           q210L           q220L           q2z0R
                                    1           q201L           q211L           q221L
      а) D = 11000101001;                 б) D = 10100111110.

    7. Найти результат применения итерации машины Т по паре состояний (qz1, qi) к слову D.
Заключительными состояниями машины Т являются qz1 и qz2. На ленте первоначально
записаны нули, а в начальной конфигурации головка указывает на левый символ входной
цепочки, состоящей из единиц.

   7.1. Машина Тьюринга задана таблицей соответствия:
                                        q0        q1        q2          q3        q4
                     T:         0       qz10E     q30E      q40E        q41R      qz21L
                                1       q10R      q20R      q00R
      a) i = 1, D = 13k,         k ≥ 1;           б) i = 1, D = 13k+2, k ≥ 1.

   7.2. Машина Тьюринга задана таблицей соответствия:
                                    q0        q1        q2       q3        q4       q5
                   T:       0       qz20R     qz20R     q30R     q41L      q50L     qz10R
                            1       q10R      q20R      q21R     q10E      q41L     q51L
      a) i = 3, D = 12k+1, k ≥ 1;         б) i = 1, D = 13k+2, k ≥ 1.

                            4. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ


      4.1. Общие сведения
    В последние три десятилетия появилось большое количество работ по общей теории
языков и грамматик. Можно выделить четыре научных направления, которые удалось
объединить по методам их исследования в одну общую задачу теории языков.
    Первое из этих направлений связано с построением формальной, или математической,
лингвистики, которая начала особенно быстро развиваться в тот период, когда были
сформулированы вопросы машинного перевода. Эта проблема требовала формализации
понятий словарь, грамматика, язык, их классификации и умения относить конкретные
словари, грамматики, языки к определенному классу.
    Интерес к задачам такого рода еще более усилился с появлением искусственных языков
программирования. С появлением трансляторов проблема перевода во многом определила
построение общей теории вычислительных машин, а сами языки программирования стали
все более приближаться к формально построенным математическим конструкциям.