INDEX

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

A

abstract, 395

accepter, 28

Ackermann’s function, 342343

algorithms, 3, 257

for blank-tape halting problem, 317f

Markov, 351354

membership, 320f, 327f

alphabets, 17

ambiguity, 140149

in grammars and languages, 145149

inherent, 148149

automata, 2, 17, 2628

configuration, 27

control unit, 27

deterministic, 2728

general characteristics, 2628

internal states, 27

nondeterministic, 28

automata classes, equivalence of, 260261

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, 1011

blank, 233

blank-tape halting problem, 315316

algorithm for, 317

BNF. See Backus-Naur form

Boolean operators, ...

Get An Introduction to Formal Languages and Automata, 6th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.