Definition:Formal Language/Alphabet

From ProofWiki
Jump to navigation Jump to search

This page is about Alphabet in the context of Formal Language. For other uses, see 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.

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.

Primitive Symbol

Let $\AA$ be the alphabet of a formal language $\LL$.

The symbols which comprise $\AA$ are called the primitive symbols of $\AA$.

It is usual, during the development of a formal system, to introduce further symbols in order to abbreviate what would otherwise be unwieldy constructions.

Hence the distinction between these newly-introduced symbols and the primitive symbols.

Also denoted as

Some sources use $\Sigma$ to denote an arbitrary alphabet.

Also see