CS Fundementals 1

A recursive defition includes:

Basis
Step
Closure

Power Set of A (P(A))

A set consiting of all possible combinations of A.

Cardinality of P(A) =

2^{|A|}

Concatenation of strings a and b (a \cdot b)

Combines strings a and b into ab.

The number of possible combinations of length L given an alphabet of length n.

n^L

Alphabet

A set of symbols.

Language

A set of strings over an alphabet.

\lambda stands for:

An empty string.

Given an alphabet \Sigma, \Sigma ^* denotes:

The set of all finite length strings over \Sigma, including \lambda.