Formal language

What is formal language?

A formal language is an abstract language used to express definitions, instructions and logic. It consists of a certain set of character or symbol chains (words), which in turn are formed from certain characters (alphabet, symbols). Formal languages are used in the fields of computer science, mathematics and linguistics.

The definition is:

A formal language L over an alphabet Σ is a subset of the Kleene's hull of the alphabet: L⊆Σ*.

The Kleene's envelope Σ* defines the set of all words that can be composed of the characters contained in alphabet A by any concatenation (concatenation of character strings). The empty word (a character string of length 0) is included.

In general, a distinction is also made between syntax and semantics in formal languages. Syntax describes the grammar of the language, i.e. the rules with which the language is composed. Semantics, on the other hand, describes the meaning of the words. The sentence: "The lamp closes the window with a cow." is syntactically correct, but semantically nonsensical. Therefore, languages need the correct cooperation of syntax and semantics.

Formal language in computer science

In theoretical computer science, formal languages are used for the ModellingThe data are used for data processing, information processing and for compiler construction. They are defined by certain replacement procedures. These are rules on how the characters of the alphabet may be combined. Common substitution procedures are, for example, Chomsky grammars, semi-Thue systems or the Lindenmayer systems.

In applied computer science, formal language is used in the form of programming languages. The source code (the entire instructions in the form of a programming language) can be created in a simple text editor. This must be translated into a suitable machine language (a binary code). Depending on the time of translation, there are various possibilities for this. A compiler is used to translate the source code before the programme is executed. A JIT compiler (just-in-time compiler) or an interpreter translates the source code while the programme is running. A combination of both is also possible and is used, for example, in the Java programming language.

Programming languages can be divided into different classes, the so-called programming paradigms. The three best-known applications of formal language are object-oriented, functional and imperative programming.

A Object-oriented programming based on data and objects. The object belongs to a superordinate class, has certain attributes and various methods are assigned to it.

With a functional programming, all components of the computer program are exclusively functions.even the programme itself. The functions can be linked to higher order functions, as in mathematics.

From a imperative programming is used when the computer program consists of instructions.which tell the computer exactly what to do and when. Loops or branches are used as control structures for this purpose.

What are examples of formal language?

1. programming languages such as:

  • C++, Java, JavaScript and Python as object-oriented programming
  • Haskell, LISP and Scheme as functional programming
  • ALGOL, Cobol, C and FORTRAN as imperative programming

2. language of palindromes: a palindrome is a word that is identical when written forwards and backwards. The formal expression is:

  • A palindrome is a word u over the alphabet Σ with the property u=uR.
  • The R operator reverses the character string.

3rd Morse sequence (also called Morse-Thue sequence, Thue-Morse sequence): is an infinite binary sequence formed according to concrete rules. As a formal language, it begins with 0, 01, 0110, 01101001, 0110100110010110...

Data Navigator Newsletter