# 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:

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

## Sources

- 1965: E.J. Lemmon:
*Beginning Logic*... (previous) ... (next): Chapter $2$: The Propositional Calculus $2$: Introduction - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next): Entry:**language** - 1993: M. Ben-Ari:
*Mathematical Logic for Computer Science*... (previous) ... (next): Chapter $1$: Introduction: $\S 1.2$: Propositional and predicate calculus - 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (next): $\S 1$: Propositional Logic - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next): Entry:**language** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**language**