Language

A language is a set of strings. It can be thought of a collection of ‘words’, though words here is not the English meaning, but descripts a sequence of characters belonging to a mathematical alphabet.

Definition §

Language ^definition

A language, $L$ is a set of formulae.

A key distinction to make is that a language can also be an empty set ($\varnothing$) or a set containing the empty word (the formula of length 0), $ϵ$. $\{ϵ\}\ne \varnothing$

Operations On Languages §

Most set operations are used when talking about languages. Let $A=\{w_1,w_2,w_3\}$ and $B=\{w_3,w_4,w_5\}$ be two languages. The following set operations are used often:

• Union: $A\cup B=\{w_1,w_2,w_3,w_4,w_5\}$
• Intersection: $A\cap B=\{w_3\}$
• (Set Difference): $A\setminus B=\{w_1,w_2\}$

However, some additional operations are defined only for languages!

Concatenation §

Language concatenation is a binary operation that works in a similar process to string concatenation in programming. It works by ‘compressing’ the cartesian product of two languages.

Let $A=\{\text{a,b}\}$ and $B=\{\text{c,d}\}$. Then:

$$A\circ B=\{\text{ac, ad, bc,bd}\}$$

This is similar (but not quite) from the Cartesian product:

$$A\times B=\{\text{(a,c), (a,d), (b,c), (b,d)}\}$$

Concatenation can be chained, and is usually represented as:

$$A^n=\underset{n\text{ times}}{\underbrace{A\circ A\circ A\circ \dots }}$$

Note: Anything concatenated with $ϵ$ yields itself, i.e. $a\circ ϵ\circ b=a\circ b$

Kleene Star §

The Kleene star is a unary function that is, essentially, infinite concatenation (similar to how exponentiation is repeated multiplication).

If $A=\{\text{a,b}\}$ then:

$$\begin{array}{rl}{A}^{\ast }& =A^0\cup A^1\cup A^2\cup \cdots =\bigcup _{i=0}^{\infty }{A}^i\\ & =\{ϵ,\text{a,b,ab,ba,aab,aba,baa,...}\}\end{array}$$

Binding Powers §

In terms of the main language operations: union, concatenation and Kleene star, the binding power order is given as:

$${}^{\ast }>\circ >\cup$$

That is, Kleene star > concatenation > union.

Some examples:

• $ab\to (a\circ b)$
• $a{b}^{\ast }\to (a\circ (b^{\ast }))$
• $a\cup b{c}^{\ast }\to (a\cup (b\circ (c^{\ast })))$

Axioms §

Axioms For Language Operations