A notation for describing machines, drafted in 1907, anticipated programming languages
In Vienna in 1907, Leonardo Torres Quevedo presented a system of symbols for describing machines. Heinz Zemanek later judged it equivalent to a programming language for controlling machine tools. It is one milestone in the long story of formal languages, which now underpin every compiler and much of theoretical computer science.
A formal language is simply a set of strings built from an alphabet of symbols. The strings are called words, and those belonging to the language are well-formed. Usually the language is specified by a grammar, such as a regular or context-free grammar. An alphabet can be any set, even an infinite one, though most theory assumes a finite alphabet like the letters of ASCII or Unicode.
The idea has deep roots. In the seventeenth century Gottfried Leibniz imagined a universal formal language written in pictographs, and Carl Friedrich Gauss later studied what are now called Gauss codes. George Boole showed in the mid-nineteenth century that reasoning could be carried out with symbolic equations, founding Boolean algebra. Gottlob Frege pursued Leibniz's dream in his Begriffsschrift of 1879 and his two-volume foundations of arithmetic.
The twentieth century sharpened the tools. Between 1906 and 1914 Axel Thue published papers on words that introduced what Emil Post named Thue systems, giving an early example of an undecidable problem; Post built on it in 1947 to show the word problem for semigroups cannot be solved by any algorithm. Noam Chomsky organised languages into the hierarchy that bears his name. In 1959 John Backus, fresh from creating FORTRAN, devised Backus–Naur form to describe programming-language syntax, and Peter Naur used it in the ALGOL 60 report.
Today formal languages define the grammars of programming languages and controlled versions of natural language. Complexity theory frames decision problems as languages and classifies them by what limited machines can recognise. Logicians use them to express axiomatic systems, and formalism holds that all of mathematics reduces to manipulating such symbols. The field itself grew out of linguistics as a way to study the structural regularities of human speech.
Source: Formal language
