Formal Language

languages

Definition

Formal Language

A (formal) language $\varnothing \ne L\subseteq {\Sigma }^{\ast }$ over an alphabet $\Sigma$ is a non-empty subset of the set of all strings ${\Sigma }^{\ast }$.

Operations

Concatenation

Definition

Language Concatenation

Let $L_1,L_2$ be two languages, then:

$$L_1\cdot L_2=\{w_1\cdot w_2\mid w_1\in \wedge w_2\in L_2\}$$

Link to original

Exponentiation

Exponentiation (Language)

Let $L$ be a language and $n\in \mathbb{N}$, then:

$$L^0=\{\epsilon \},L^{n+1}=L\cdot L^n$$

Kleene Star

Definition

Kleene Star

$$\begin{array}{rl}{L}^{\ast }& =\bigcup _{n\ge 0}{L}^n=\{\epsilon \}\cup L^{+}\\ L^{+}& =\bigcup _{n\ge 1}{L}^n\end{array}$$

Link to original