David Keil                                                      

Theory of Computing                                  

Spring 2010

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 sometimes be different from in the textbook. We will present a variety of notations that may denote the same thing.


Logic

Ψ                   not

Ω                   and

Ϊ          or

ή                implication

"                   Universal quantification (for all)

$                    Existential quantification (there exists)

Set theory

Ξ         set membership

Ο                   nonmembership

Ζ         null set

{}        null set

Ν         subset

Μ         proper subset

Θ         union

Η         intersection

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

ΐ0 denotes aleph null, the cardinality of countable sets.

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

Formal languages

A string over S is a sequence of symbols chosen from alphabet S.

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

l = e = null string. l and e are also used to denote automata state transitions that don’t consume inputs.

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

 (L1 + L2) = (L1 | L2) = (L1 Θ L2) (language union)

L1 L2 = { xz | x Ξ L1 , z Ξ  L2} (concatenation of languages)

L* = { x1 x2 . … xn | x1, z2, … zn Ξ  L}

Greek alphabet

Used often to denote objects in mathematics

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