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

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

T
2
: 0 q
21
1L q
2z
0R
1 q
21
1L q
20
0L
а) D = 111100111011; б) D = 11010111.
6.2. Машины Т
1
и Т
2
заданы таблицами соответствия:
q
10
q
11
q
12
T
1
: 0 q
11
0R q
12
0R q
1z
1L
1 q
10
1R q
10
1R
q
20
q
21
q
22
T
2
: 0 q
21
0L q
22
0L q
2z
0R
1 q
20
1L q
21
1L q
22
1L
а) D = 11000101001; б) D = 10100111110.
7. Найти результат применения итерации машины Т по паре состояний (q
z1
, q
i
) к слову D.
Заключительными состояниями машины Т являются q
z1
и q
z2
. На ленте первоначально
записаны нули, а в начальной конфигурации головка указывает на левый символ входной
цепочки, состоящей из единиц.
7.1. Машина Тьюринга задана таблицей соответствия:
q
0
q
1
q
2
q
3
q
4
T: 0 q
z1
0E q
3
0E q
4
0E q
4
1R q
z2
1L
1 q
1
0R q
2
0R q
0
0R
a) i = 1, D = 1
3k
, k ≥ 1; б) i = 1, D = 1
3k+2
, k ≥ 1.
7.2. Машина Тьюринга задана таблицей соответствия:
q
0
q
1
q
2
q
3
q
4
q
5
T: 0 q
z2
0R q
z2
0R q
3
0R q
4
1L q
5
0L q
z1
0R
1 q
1
0R q
2
0R q
2
1R q
1
0E q
4
1L q
5
1L
a) i = 3, D = 1
2k+1
, k ≥ 1; б) i = 1, D = 1
3k+2
, k ≥ 1.
4. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ
4.1. Общие сведения
В последние три десятилетия появилось большое количество работ по общей теории
языков и грамматик. Можно выделить четыре научных направления, которые удалось
объединить по методам их исследования в одну общую задачу теории языков.
Первое из этих направлений связано с построением формальной, или математической,
лингвистики, которая начала особенно быстро развиваться в тот период, когда были
сформулированы вопросы машинного перевода. Эта проблема требовала формализации
понятий словарь, грамматика, язык, их классификации и умения относить конкретные
словари, грамматики, языки к определенному классу.
Интерес к задачам такого рода еще более усилился с появлением искусственных языков
программирования. С появлением трансляторов проблема перевода во многом определила
построение общей теории вычислительных машин, а сами языки программирования стали
все более приближаться к формально построенным математическим конструкциям. 
                           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. Общие сведения
    В последние три десятилетия появилось большое количество работ по общей теории
языков и грамматик. Можно выделить четыре научных направления, которые удалось
объединить по методам их исследования в одну общую задачу теории языков.
    Первое из этих направлений связано с построением формальной, или математической,
лингвистики, которая начала особенно быстро развиваться в тот период, когда были
сформулированы вопросы машинного перевода. Эта проблема требовала формализации
понятий словарь, грамматика, язык, их классификации и умения относить конкретные
словари, грамматики, языки к определенному классу.
    Интерес к задачам такого рода еще более усилился с появлением искусственных языков
программирования. С появлением трансляторов проблема перевода во многом определила
построение общей теории вычислительных машин, а сами языки программирования стали
все более приближаться к формально построенным математическим конструкциям.

Страницы