# Definition:Formal Language

## Definition

A **formal language** is a structure $\mathcal L$ which comprises:

- A set of symbols $\mathcal A$ called the alphabet of $\mathcal L$
- A collation system with the unique readability property for $\mathcal A$
- 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 $\mathcal L$ be a formal language.

The **alphabet** $\mathcal A$ of $\mathcal L$ is a set of symbols from which collations in $\mathcal L$ may be constructed.

An **alphabet** consists of the following parts:

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

#### Letter

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

#### Sign

A **sign** of a formal language $\mathcal L$ 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 $\mathcal L$ be a formal language whose alphabet is $\mathcal A$.

The **formal grammar** of $\mathcal L$ comprises of rules of formation, which determine whether collations in $\mathcal A$ belong to $\mathcal L$ or not.

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

## Sources

- 1965: E.J. Lemmon:
*Beginning Logic*... (previous) ... (next): $\S 2.1$: Introduction - 1993: M. Ben-Ari:
*Mathematical Logic for Computer Science*(1st ed.) ... (previous) ... (next): $\S 1.2$: Propositional and predicate calculus - 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (next): $\S 1$: Propositional Logic