A formal language consists of sequences of strings which are taken from a given alphabet. A formal languages can also be thought of as a set of different strings formed from characters from an alphabet.

Notation

Let be an alphabet. For each natural , let

• the set of all strings over that have length
• the set of all strings over that have a length of at least 1
• the set of all strings over

All of these notations represent different formal languages of the alphabet .

Operations

Concatenation

Given two languages and the concatenation of the two languages can be written as or informally . The concatenation of two languages represents the outcome of writing every string in followed by every string of . This operation can written using set builder notation as .

Example

Given the languages and the concatenation of and written as is the following

This operation can more easily be performed using a table where the combination elements are written in the centre of the table from each column and row.