Ginsburg S. — The mathematical theory of context-free languages :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Ginsburg S. — The mathematical theory of context-free languages

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: 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

Предметный указатель

$\epsilon$ -free grammar      38
$\omega$ -maximal      203
$\Sigma$ -word      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- $\epsilon$ word      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

1 2

О проекте