An Introduction to Formal Languages and Automata, 6th Edition

INDEX

Note: Page numbers followed by f indicate material in figures.

A

abstract, 395

accepter, 28

Ackermann’s function, 342–343

algorithms, 3, 257

for blank-tape halting problem, 317f

Markov, 351–354

membership, 320f, 327f

alphabets, 17

ambiguity, 140–149

in grammars and languages, 145–149

inherent, 148–149

automata, 2, 17, 26–28

configuration, 27

control unit, 27

deterministic, 27–28

general characteristics, 26–28

internal states, 27

nondeterministic, 28

automata classes, equivalence of, 260–261

automaton, 2

axioms, 346, 348

B

Backus-Naur form (BNF), 151, 152

base of cycle, 9

basis for induction, 10, 11

binary adder, 33

binary tree, 10–11

blank, 233

blank-tape halting problem, 315–316

algorithm for, 317

BNF. See Backus-Naur form

Boolean operators, ...