Lawson M.V. Finite Automata
Подождите немного. Документ загружается.
< previous page page_305 next page >
Page 305
induction hypothesis (in induction), 280
infinite semigroup, 186
initial state, 14
injective function, 289
input alphabet, 14
interior vertex, 288
intersection, 284
n (intersection), 284
inverse of element, 239
invertible element, 239
isomorphic automata, 153
isomorphism (automaton), 153
isomorphism (group), 241
isomorphism (semigroup), 196
kernel, 199
Kleene star of language, 8
Kleene’s Theorem, 103
Krohn-Rhodes Theorem, 262
language, 6
language accepted by automaton, 17
language generated by grammar, 79
language hierarchy, 84
language learning, 49
language recognised by automaton, 17
language recognised by monoid, 226
leading diagonal (of matrix), 286
leaf of tree, 288
left congruence, 206
left ideal, 218
left quotient of language, 157
lemma, 281
length of string, 3
letter (of alphabet), 1
lexicographic, 4
lexicon, 4
linear order, 292
linear regular expression, 135
linearisation of regular expression, 135
list, 285
local automaton, 128
local language, 129
local monoid, 243
local standard automaton, 128
locally testable language, 277
matrix, 286
matrix multiplication, 286
maximal group, 244
Mealy machine, 22
Method of Quotients, 162
minimal automaton (for language), 155
minimal left ideal, 245
modulo (a number), 34
monoid, 186
monoid homomorphism, 93
monoid of representatives, 188
Moore machine, 22
Myhill graph, 128
Myhill-Nerode relation, 214
Myhill-Nerode Theorem, 214
, 283
natural function, 199
natural homomorphism, 203
necessary and sufficient condition, 280
necessary condition, 280
non-deterministic automaton, 61
non-terminal symbol (grammar), 78
normal subgroup, 249
normalised (generalised) automaton, 109
normalised
ε
-automaton, 106
, 282
odd number, 286
order of group, 239
ordered pair, 285
partial function, 290
partial injection, 290
partial order, 292
partition, 141
path (in graph), 287
< previous page page_305 next page >
< previous page page_306 next page >
Page 306
period of element, 250
permutation, 238
piecewise testable language, 277
plus (+) operation, 3
powerset, 283
P
(A)
(powerset), 283
prefix, 3
Prefix
(L),
75
preorder, 219
presentation, 183
prime number, 286
product (of sets), 285
× (product of sets), 285
product matrix, 286
product of semigroup, 222
product operation of languages, 8
production (grammar), 79
projection homomorphism, 222
proof by induction, 280
proper factor, 3
proper ideal, 218
proper prefix, 3
proper subset, 283
proper suffix, 3
proposition, 281
pseudovariety, 266
pseudovariety generated by monoids, 269
pseudovariety of semigroups, 277
Pumping Lemma, 46
, 283
quotient of language, 158
quotient semigroup, 202
, 283
rank of element in monoid, 255
rank of language, 157
rational transduction, 23
recognisable language, 17
recursively enumerable language, 79
reduced automaton, 145, 146
reduction of an automaton, 147
reflexive relation, 291
regular expression, 98
regular language, 100
regular operator, 98
relation, 290
relative complement, 284
\ (relative complement), 284
Remainder Theorem, 33, 286
reset semiautomaton, 262
restriction (of function), 290
reverse of language, 60
reverse of string, 60
reversible automaton, 49
right congruence, 206
right ideal, 218
right linear grammar, 80
right linear language equation, 115
right quotient of language, 157
rooted tree, 287
S(X),
238
S(n),
238
Schützenberger product, 229
Schützenberger’s Theorem, 258
Second Isomorphism Theorem, 214
semiautomaton, 23
semigroup, 185
semilattice, 274
sequence, 285
sequential function, 23, 207, 263, 278
set, 281
ShortLex order, 4
Σ, 285
similar regular expressions, 165
simple graph, 287
simple group, 262
simple grouplike semiautomaton, 262
sink state, 31
star (*) operation, 3
star-free expression, 235
star-free language, 236
start symbol (grammar), 78
state, 14
statement, 279
strictly alphabetic homomorphism, 132
< previous page page_306 next page >
< previous page page_307
Page 307
string, 1
subgroup, 239
submonoid, 193
subsemigroup, 193
subsemigroup generated by a subset, 194
subset, 283
(subset), 283
subset construction, 63
subset product (in semigroup), 187
substring, 3
sufficient condition, 280
suffix, 3
Suffix
(L),
75
surjective function, 289
symbol (of alphabet), 1
symmetric group, 240
symmetric matrix, 286
symmetric relation, 291
syntactic congruence, 210
syntactic monoid, 210
syntactic semigroup, 207, 277
T(X),
174
Tn,
174
table form of equivalence relation, 144
table of representatives, 180
terminal state, 14
terminal symbol (grammar), 78
theorem, 281
Third Isomorphism Theorem, 214
token (of computer language), 2
transition diagram, 14
transition function, 14
transition monoid, 188
transition table, 15
transition tree, 57
transitive relation, 291
transpose (of matrix), 286
tree, 287
tree of strings, 4
tree order, 4
trim automaton, 73
trim part, 73
trivial group, 239
Turing machine, 50
two-sided ideal, 218
ultimately periodic, 106
unary operation, 289
union, 284
or + (union), 284
union of partial functions, 290
universe, 285
up to isomorphism (semigroup), 196
variety (of languages), 270
Variety Theorem, 271
vertex, 287
well-formed automaton, 16
, 283
zero (in semigroup), 186
, 34
< previous page page_307