Составители:
256
, описание конечное 28
входной 6
выражений арифметических 80
естественный 5, 13
конечный 9, 43, 46, 57, 59
контекстно-зависимый 20, 21, 119, 120−123,
127, 128, 132, 133, 135
контекстно-свободный 3, 6, 20, 21, 50, 51, 54,
57, 59, 61, 65, 66, 68, 76, 77, 102, 117, 122,
125, 127, 132, 135, 237−240
детерминированный 239
КС 46, 64, 65, 69, 70
нерегулярный 46
линейный 65
над алфавитом 9
не контекстно-зависимый 122
перечислимый рекурсивно 11
неоднозначный существенно 66, 239
непустой 48
ограниченный 66, 68
Паскаль 12, 27, 42, 43, 45
, числа без знака 27, 45
перечислимый рекурсивно 11, 12
, порождаемый грамматикой 15, 26, 28, 80
, последовательной 65
, типа 0 92, 113, 114
, 3 19, 28, 36, 38
последовательный 65, 68
, принимаемый автоматом 31, 32, 71, 73, 90,
118, 120
, конечным 31, 32
, линейно ограниченным 118, 120
, магазинным при магазине пустом 71
, состоянии конечном 71
, МП 70, 73
, недетерминированным 70
, при магазине пустом 73
, состоянии конечном 73
, машиной Тьюринга 84, 92, 96, 97, 112−
114
, детерминированной 97
, многоленточной 96
, недетерминированной 97
, одноленточной, 96
программирования 5, 13, 137, 240
, синтаксис 64
пустой 26, 46−48, 71, 93, 102
, распознаваемый 28, 29, 69, 80, 92, 113, 114,
116
, автоматом 28, 29, 69, 80
, конечным 28, 29
, магазинным 69, 80
, при состоянии конечном 80
, машиной Тьюринга 92, 116, 113, 114
, процедурой 9
регулярный 19, 21, 61, 63, 67, 102, 117, 132
рекурсивный 11, 12, 92, 121, 122
русский 137
типа 0 6, 19, 28, 123, 132, 133
1 6, 28
2 28
3 19, 28, 43
формальный 6, 8, 241
LL(k) 6
LR(k) 6
Ячейка 28, 29, 33, 82, 83, 89, 90, 94−97, 100−102,
109, 110, 113, 118−120, 163
accept 164−167, 175, 190, 204−206, 224, 225,
227, 232, 236
A-порождение 54, 55, 67
леворекурсивное 54
A-правило 64, 172
, часть правая 64
cfg (context-free grammar) 18, 19, 26, 27, 48, 50,
55, 65, 66−67, 77−80, 117, 124, 155, 161, 165,
172, 174, 179, 184, 208, 223, 225
cfl (context-free language) 19, 55, 68, 79, 84, 103,
135
csg (context-sensitive grammar) 17,19, 27, 92, 93,
120, 122, 124, 128
csl (context-sensitive language) 19, 129
dfa (deterministic finite automaton) 29, 34, 36, 37,
38, 39, 41, 45, 125
, управление конечное 125
dpdt (deterministic pushdown transducer) 142,
150, 151, 154, 166, 193, 194, 232−234
, магазин типа “first-in-last-out” 234
error 164, 165, 167, 172, 173, 175, 190, 204, 205,
224−226, 232
fa (finite automaton) 28, 29, 31−33, 35−37, 39−41,
43, 45, 125
GOTO 214, 215, 220, 221, 225, 232
gsm (generalized sequential machine) 130, 131,
135
отображение 130−132, 134
обратное 130−133
ε-свободное 134
ε-свободное 132
l
ba (linear-bounded automaton) 118−122, 126, 135
N(M) 71−81
ndfa (nondeterministic finite automaton) 33−37,
40, 41
npda (nondeterministic push-down automaton) 70,
125
движение , след состояний 125