David Keil

Theory of Computing

Spring 2009

Notation

Notation varies in the relatively new field of theoretical computer science. The slides, handouts, and exams in this course will use a notation that may be sometimes different from in the textbook. We will present a variety of notations that denote the same thing.

l = e = null string

l is also used to denote transitions on DFAs without consuming inputs, and the stack actions of popping empty stack and pushing nothing on the stack (not the same as pushing the null string).

Æ = {} = null set

À₀ denotes aleph null, the cardinality of countable sets.

À₁ denotes aleph one, the cardinality of the sets of reals, predicates, streams, or functions on natural numbers.

S is normally a finite alphabet; S^* is the set of all strings over S

S^¥ is the set of all steams (infinite sequences) over S

Language union: (0 + 1) = (0 | 1) = (0 È 1)

Concatenation of languages

L₁ L₂ = { xz | x Î L₁ , z Î L₂}

L* = { x₁ x_{2 .} … x_n | x₁, z₂, … z_n Î L}

A ´ B is the Cartesian product of sets A and B, i.e., all ordered pairs áx, yñ such that x is in A, y is in B

Symbols in set theory and logic:

Ø not

Ù and

Ú or

Î set membership

Ï nonmembership

Í subset

Ì proper subset

È union

Ç intersection

Greek alphabet:

a alpha

b beta

c chi

d delta

e epsilon

f phi

g (G) gamma

h nu

i iota

j psi

k kappa

l lambda

m mu

n

o

p pi

q theta

r rho

s (S) sigma

t tau

u

v

w omega

x xi

z