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.

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$.


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.