Formal language

For a finite set $\Sigma$ of symbols, we call $\Sigma$ an alphabet. Then we also define:

• A string (or sentence) as a sequence of alphabet symbols.
• ${\Sigma }^n$ is the set of all strings over $\Sigma$ that have length $n$.
• ${\Sigma }^{+}$ is the set of all strings over $\Sigma$ with length at least 1 (i.e., excluding the empty string $ϵ$), called the positive closure.
• ${\Sigma }^{\ast }$ is the set of all strings over $\Sigma$, called the Kleene closure. This includes the empty string. Practically speaking, this is a repetition.
  • For a language $L_1=\{a\}$, the Kleene star is any $L_1^{\ast }=\{\varnothing ,a,aa,aaa,\cdots \}$.

In discrete mathematics and computer science, a formal language over the alphabet $\Sigma$ is any set $\mathcal{L}\in {\Sigma }^{\ast }$, i.e., any set of strings of characters of the alphabet. Defining formal languages allows us to explore regular expressions.

The concatenation of $\mathcal{L}$ and ${\mathcal{L}}^{\prime }$ is the set:

$$\mathcal{L}{\mathcal{L}}^{\prime }=\{xy\mid x\in \mathcal{L}\cap y\in {\mathcal{L}}^{\prime }\}$$

The union of $\mathcal{L}$ and ${\mathcal{L}}^{\prime }$ is:

$$\mathcal{L}\cup {\mathcal{L}}^{\prime }=\{x\mid x\in \mathcal{L}\cap {\mathcal{L}}^{\prime }\}$$