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$.
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): 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): formal language
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): language
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): formal language
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): language