David Keil                                                          Theory of Computing                                                        Spring 2006

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

À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.

Cohen denotes starting state of a DFA with minus sign in state circle, accept states with plus sign. Many other sources denote start state with arrow going from nowhere to this state, accept states with circle around state circle.

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

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

 

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

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

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

Some symbols in set theory and logic:

Ø                   not

Ù                   and

Ú         or

Π        set membership

Ï         nonmembership

Í         subset

Ì         proper subset

È         union

Ç         intersection