Авторизация
Поиск по указателям
Ginsburg S. — The mathematical theory of context-free languages
Обсудите книгу на научном форуме Нашли опечатку?
Название: The mathematical theory of context-free languagesАвтор: Ginsburg S. Аннотация: The Concept of a Context-free Language was first introduced by Chomsky in 1959 [Ch 3] (Refers to N. Chomsky, 3d listing, in the References and Related Papers" at the end of the book. The same shorthand form used in the text, for example, [Ch 3], precedes the corresponding entry in the "References.") in an attempt to find a reasonable mathematical model of natural languages such as English, French, etc. In the period 1959-1960, several papers developing the theory were written [Ch 3, 4; CM; BGS; BPS]. In late 1960, it was discovered that the "ALGOL-like" languages, that is, the languages defined by Backus normal form (the metalanguage used to describe the widely publicized programming language ALGOL-60), were identical with the context-free languages. Since then, there has been a flurry of activity in the theoretical development of context-free languages..." [from the preface]
Язык: Рубрика: Математика /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Год издания: 1966Количество страниц: 245Добавлена в каталог: 09.12.2012Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
38 203 2 * operation 2 Accepted 47 50 61 73 Additive operation 106 Algol-like language 15 Algorithm 115 Alphabet 2 Alternate shuffle 108 Altman, E.B. 51 118 Ambiguous grammar 31 139 183 Associated pda and pdt 104 Automaton 47 Backus normal form (BNF) 13 Banerji, R.B. 51 118 Bar-Hillel, Y. 18 23 45 82 114 118 127 128 140 Bauer, F.L. 82 Beckenbach, E.F. 5 Biadditive function 107 Binary standard form 23 34 BNF 13 Bounded output 98 Bounded set 141 Brzozowski, J.A. 109 Burks, A.W. 82 c-finite language 58 126 Cantor, D.G. 45 140 Caracciolo, A. 15 Cartesian product 2 Chomsky, N. 7 9—11 23 31 45 54 55 82 114 140 168 211 Clifford, A.H. 36 Coefficient 14 Cole, S.N. 169 Commutative set 169 Complement 1 79 Complementary language 96 128 Complementation 1 Complete sequential machine (csm) 94 Complex product of sets 2 Complex product of words 2 Concatenation 2 Congruence relation 50 Constant 143 Contain a sequence 128 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 CSM 94 102 127 134 135 d-accepted 75 Davis, M. 10 115 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 Drooyan, I. 5 Dyck language 11 110 Effective calculation 115 Effective procedure 115 Elgot, C.C. 51 95 108 114 134 Empty set 1 Empty word 2 Equality of sets 1 117 126 182 Equality of words 2 Equivalence class 3 Equivalence relation 3 Ershov, A.P. 82 Evey, R.J. 45 46 63 82 105 114 Extension of a node 25 Fabian, V. 35 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 Fischer, P.C. 82 Floyd, R.W. 12 15 45 140 Formal polynomial 35 Free semigroup 2 FSA 47 Function into 3 Function onto 3 Gaifman, H. 18 Generalized pda 62 Generalized sequential machine (gsm) 93 Generate 9 Generation 9 Generation tree 24—29 Ginsburg, S. 18 35 45 46 51 54 55 80—82 87 90 96 102 105 106 108 109 114 118 127—129 134 135 140 157 168 169 176 183 184 207 208 211 Gladkii, A.V. 73 Grammar 10 Grammatical element 35 Greatest common divisor 5 Greibach, S.A. 63 72 81 82 97 128 129 140 169 Griffiths, T.V. 71 GSM 93—102 127 176 200 207 208 211 gsm mapping 94—102 129—135 gsm mapping theorem 94 Haines, L.H. 10 72 82 90 168 208 211 Harrison, M.A. 35 80 Hibbard, T.N. 51 87 118 128 129 134 135 211 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 Kasami, T. 130 Kleene, S.C. 81 Knuth, D.E. 63 74 75 81 Konig, D. 184 Kuroda, S.Y. 10 73 81 Label 4 Landweber, P.S. 10 73 Language 10 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 Matthews, G.H. 72 MAX 5 Maximal element 3 Maximal node 25 Metalinear grammar 54 Metalinear language 54 Mezei, J.E. 95 114 Miller, G.A. 82 MIN 5 Minimal element 3 Minimal fixed point 18 Minimal generation tree 25 Minimal linear grammar 140 168 Minimal positive solution 179 Move 60 Myhill, J. 10 73 82 n-tuple standard function 14 Naur, P. 12 45 Newell, A. 82 Next-state function 47 93 Node 4 Node in path 4 Node names 4 Non- 2 Nondenumerable 3 Nondeterministic automaton 49 Nondeterministic finite-state acceptor 49 Nondeterministic finite-state automaton 49 Nondeterministic fsa 49 Nonlanguage 83—87 96 149 167 168 Nonmaximal node 25 Nonterminal 8 Nonterminal bounded grammar 51 118 Null (M) 63—72 80 90 Oettinger, A.G. 35 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 Ozaki, H. 130 Parenthesis-free language 35 Parikh theorem 146 Parikh, R.J. 45 146 184 211 Parsing diagram 24 Parsing tree 24 Partial order 3 Partially ordered set 3 Path 4 PDA 59—82 90 97 104 pdt 103—105 135—139 Period 143 Perles, M. 23 45 82 114 118 127 128 140 Petrick, S.R. 71 Phrase-structure grammar 8 97 Phrase-structure language 9 Positive solution 177 Post correspondence theorem 119 Post, E.L. 119 140 Precedence grammar 12 Presburger formula 183 Presburger sentence 184 Presburger set 184 Preserve languages 83 Preserve regular sets 83 Preston, G.B. 36 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 Rabin, M.O. 51 81 126 140 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 Rice, H.G. 18 45 54 114 Right-linear grammar 52 126 140 Right-linear language 52 Right-linear production 52 Right-quotient 108 109 127 Rightmost derivation 30 72 Root 4 Rose, G.F. 51 55 87 90 102 105 106 108 114 135 140 157 Rutledge, J.D. 108 Samelson, K. 82 Scheinberg, S. 87 114 Schorre, D.V. 34 139 Schutzenberger, M.P. 35 54 82 140 211 Scott, D. 51 81 126 140 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 Shamir, E. 18 23 45 54 59 82 114 118 127 128 140 Shaw, J.C. 82 Shuffle 108 Simple order 3 Solution 15 177 Solvability 115—118 174—184 Spanier, E.H. 108 109 127 157 168 176 184 Standard function 14 Stanley, R.J. 114 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 Terminal letter 8 Terminal subpath 4 Terminal subword 2 Torii, K 130 Transformation 3
Реклама
-free grammar 
-maximal 
-word 
|
|
О проекте