Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 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. Общие сведения
В последние три десятилетия появилось большое количество работ по общей теории
языков и грамматик. Можно выделить четыре научных направления, которые удалось
объединить по методам их исследования в одну общую задачу теории языков.
Первое из этих направлений связано с построением формальной, или математической,
лингвистики, которая начала особенно быстро развиваться в тот период, когда были
сформулированы вопросы машинного перевода. Эта проблема требовала формализации
понятий словарь, грамматика, язык, их классификации и умения относить конкретные
словари, грамматики, языки к определенному классу.
Интерес к задачам такого рода еще более усилился с появлением искусственных языков
программирования. С появлением трансляторов проблема перевода во многом определила
построение общей теории вычислительных машин, а сами языки программирования стали
все более приближаться к формально построенным математическим конструкциям.