|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Ginsburg S. — The mathematical theory of context-free languages |
|
|
|
| Предметный указатель |
Accepted 47 50 61 73
Additive operation 106
Algol-like language 15
Algorithm 115
Alphabet 2
Alternate shuffle 108
Ambiguous grammar 31 139 183
Associated pda and pdt 104
Automaton 47
Backus normal form (BNF) 13
Biadditive function 107
Binary standard form 23 34
BNF 13
Bounded output 98
Bounded set 141
Cartesian product 2
Cartesian product,  -finite language 58 126
Coefficient 14
Commutative set 169
Complement 1 79
Complementary language 96 128
Complementation 1
Complete sequential machine (csm) 94
Complex produet of sets 2
Complex produet of words 2
Concatenation 2
Congruence relation 50
Constant 143
Contain a sequence 128 229
Context-bounded grammar 140
Context-dependent grammar 9
Context-dependent language 9
Context-free grammar 10
Context-free language 10
Context-sensitive grammar 9
Context-sensitive language 9 11 73 81
Correspondence problem 119 127
Correspondence problem, csm 94 102 127 134 135
Correspondence problem, d-accepted 75
Decision procedure 115—140 169—184 208—211
Denumerable 3
Denumerably infinite 3
Depend 19
Dependency lemma 19
Derivation 9
Derivative 109
Deterministic language 74—81 87 128 168
Deterministic lba 81
Deterministic PDA 74—81 126 129
Difference theorem 89
Directed line 4
Disjoint sets 1
divides 5
Dyck language 11 110
Effective calculation 115
Effective procedure 115 230
Empty set 1
Empty word 2
Empty word, t-free grammar 38
Equality of sets 1 117 126 182
Equality of words 2
Equivalence class 3
Equivalence relation 3
Extension of a node 25
Final state 47 50 59
Finite directed graph 3
Finite directed labeled graph 4
Finite rooted directed tree with labeled, nodes 4
Finite-state acceptor (fsa) 47
Finite-state automaton 47
Finite-state language 49
Formal polynomial 35
Free semigroup 2
Free semigroup, fsa 47
Function into 3
Function onto 3
Generalized pda 62
Generalized sequential machine (gsm) 93
Generate 9
Generation 9
Generation tree 24—29
Grammar 10
Grammatical element 35
Greatest common divisor 5
Greatest common divisor, gsm 93—102 127 176 200 207 208 211
Greatest common divisor, gsm mapping 94—102 129—135
Greatest common divisor, gsm mapping theorem 94
Homomorphism 36 37 51 54 58 110— 114 128 211
Incomparable elements 3 163
INDEX 50
Inherently ambiguous language 33 185—211
Init(x) 87 107 128
Initial subword 2
Input 47 49 59 91 93
Intersection 1 73 81 88 120 127 180 181
Intersection theorem 88
Inverse of a sequential transducer 96
Label 4
Language 10
Language, lba 73
Left-linear grammar 52
Left-linear language 52
Left-linear production 52
Left-literal production 72
Left-quotient 109
Leftmost derivation 30
Length of derivation 9
Length of generation 9
Length of path 4
Length of word 2
letter 8
Linear bounded acceptor (lba) 73
Linear bounded automaton 73
Linear function 176
Linear grammar 51
Linear language 51 54 96 128
Linear production 51
Linear set 144 163—169 183 215
Linearly dependent 5 143
Linearly independent 5 143
Loop-free deterministic pda 76—79
Mapping 3
Mapping, max 5
Maximal element 3
Maximal node 25
Metalinear grammar 54
| Metalinear language 54
Metalinear language, min 5
Minimal element 3
Minimal fixed point 18
Minimal generation tree 25
Minimal linear grammar 140 168
Minimal positive solution 179
Move 60
Next-state function 47 93
Node 4
Node in path 4
Node names 4
Non-t word 2
Nondenumerable 3
Nondeterministic automaton 49
Nondeterministic finite-state acceptor 49
Nondeterministic finite-state automa, ton 49
Nondeterministic fsa 49 231
Nonlanguage 83—87 96 149 167 168
Nonmaximal node 25
Nonterminal 8
Nonterminal bounded grammar 51 118
Nonterminal bounded grammar, w-tuple standard function 14
Null (AT) 63—72 80 90
One-to-one function 3 101 102 205 206
Operation 3 36 49 83—114 129—139
Operator grammar 12
Output 91 93 103
Output function 94
Parenthesis-free language 35
Parikh theorem 146
Parsing diagram 24
Parsing tree 24
Partial order 3
Partially ordered set 3
Path 4
Path, pda 59—82 90 97 104
Path, pdt 103—105 135—139
Period 143
Phrase-structure grammar 8 97
Phrase-structure language 9
Positive solution 177
Post correspondence theorem 119
Precedence grammar 12
Presburger formula 183
Presburger sentence 184
Presburger set 184
Preserve languages 83
Preserve regular sets 83
Product of sets 2
Product of words 2
Production 8
Pushdown acceptor (pda) 59
Pushdown automaton 59
Pushdown store 59
Pushdown symbol 59
Pushdown tape 59
Pushdown transducer (pdt) 103
Quasi-deterministic pda 74
realized 9 24 60 103
Recursive set 10 115
recursive solution 115
Recursive solvability 115
Recursive unsolvability 115
Reduced grammar 21
Reflection 19
Regular of class 2 59
Regular set 47—59 63 72 80 86 88 92 100 105 111 117 126 129—135 199—206
Relation 2
Relatively prime integers 5
reverse 19
Rewriting rule 8
Rewriting system 8
Right-linear grammar 52 126 140
Right-linear language 52
Right-linear production 52
Right-quo tient 108 109 127
Rightmost derivation 30 72
Root 4
Self-embedding grammar 55
Self-embedding variable 55
Semilinear set 144
Sequential grammar 54
Sequential language 54 59 157
Sequential transducer 91—96
Sequential transducer mapping 91
Set intersection 1
Set union 1
Shuffle 108
Shuffle,  word 2
Simple order 3
Solution 15 177
Solvability 115—118 174—184
Standard function 14
Standard function, operation 2
Start pushdown symbol 59
Start state 47 50 59 91 94
State 47 49 59 91 93
Stratified set 159
Structure of a grammatical element 35
Subset 1
Substitution 36 49 51 87
Substitution theorem 36 49
Subtree generated by a node 26
Subword 2
Term 14
Terminal 8
Terminal grammatical element 35 232
Terminal letter 8
Terminal subpath 4
Terminal subword 2
Transformation 3
Ultimately periodic sequence 3
Ultimately periodic set 3 48 86 87
Unambiguous grammar 31 38 42 72 139
Unambiguous language 33 54 69 79 80 88 96 186—208
Unambiguous pda 69
Undecidability 115
union 1
Unrestricted rewriting grammar 72
Unsolvability 115—140 208—211
Variable 8
Vector 4
Vector of length k 2
Vector, to-maximal 203
Vector, word 2
|
|
|
| Реклама |
|
|
|
|
|
О проекте