Definition:Formal Language

From ProofWiki
Jump to navigation Jump to search


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.


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.

Depending on the specific nature of any particular formal language, these too may be subcategorized.


A letter of a formal language is a more or less arbitrary symbol whose interpretation depends on the specific context.

In building a formal language, letters are considered to be the undefined terms of said language.

An important part of assigning semantics to a formal language is to provide an interpretation for its letters.


A sign of a formal language $\LL$ is a symbol whose primary purpose is to structure the language.

In building a formal language, signs form the hooks allowing the formal grammar to define the well-formed formulae of the formal language.

Common examples of signs are parentheses, "(" and ")", and the comma, ",".

The logical connectives are also signs.

Signs form part of the alphabet of a formal language.

Unlike the letters, they must be the same for each signature for the language.

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 see

  • Results about formal languages can be found here.