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