# Definition:Formal Language

## Definition

A formal language is a structure $\LL$ which comprises:

A set of symbols $\AA$ called the alphabet of $\LL$
A collation system with the unique readability property for $\AA$
A formal grammar that determines which collations belong to the formal language and which do not.

Often, the collation system is left implicit, and taken simply to match the formal grammar.

### Alphabet

Let $\LL$ be a formal language.

The alphabet $\AA$ of $\LL$ is a set of symbols from which collations in $\LL$ may be constructed.

An alphabet consists of the following parts:

The letters
The signs.

### Collation System

A key feature of collations is the presence of methods to collate a number of collations into a new one.

A collection of collations, together with a collection of such collation methods may be called a collation system.

For example, words and the method of concatenation.

### Formal Grammar

Let $\LL$ be a formal language whose alphabet is $\AA$.

The formal grammar of $\LL$ comprises of rules of formation, which determine whether collations in $\AA$ belong to $\LL$ or not.

Roughly speaking, there are two types of formal grammar: top-down grammar and bottom-up grammar.

## Also defined as

Some sources state that:

the alphabet $\AA$ must be a finite set for $\LL$ to be classified as a formal language
the formal language can consist of any arbitrary set of strings from $\AA$.

Some sources state that:

the alphabet $\AA$ must be a finite set for $\LL$ to be classified as a formal language
the formal language can consist of any arbitrary set of strings from $\AA$.

## Examples

### Empty Set forms Formal Language

The empty set $\O$ forms a formal language.

### Set of Null Strings forms Formal Language

The set consisting of the null string $\epsilon$ forms a formal language.

### Set of Palindromes over $\set {0, 1}$ forms Formal Language

The set of palindromes over $\set {0, 1}$ forms a formal language.

## Also see

• Results about formal languages can be found here.