formal_language.md

   1 # Formal Language
   2
   3 The field of formal languages tries to [mathematically](math.md) and rigorously view problems as languages; this includes probably most structures we can think of, from human languages and computer languages to visual patterns and other highly abstract structures. Formal languages are at the root of theoretical [computer science](compsci.md) and are important e.g. for the theory of [computability](computability.md)/decidability, computational complexity, [security](security.md) and [compilers](compiler.md), but they also find use in linguistics and other fields of [science](science.md).
   4
   5 A **formal language** is defined as a (potentially infinite) set of strings (which are finite but unlimited in length) over some alphabet (which is finite). I.e. a language is a subset of E* where E is a finite alphabet (a set of *letters*). (* is a *Kleene Star* and signifies a set of all possible strings over E). The string belonging to a language may be referred to as a *word* or perhaps even *sentence*, but this word/sentence is actually a whole kind of *text* written in the language, if we think of it in terms of our natural languages. The [C](c.md) programming language can be seen as a formal language which is a set of all strings that are a valid C program that compiles without errors etc.
   6
   7 **For example**, given an alphabet [a,b,c], a possible formal language over it is [a,ab,bc,c]. Another, different possible language over this alphabet is an infinite language [b,ab,aab,aaab,aaaab,...] which we can also write with a [regular expression](regex.md) as a*b. We can also see e.g. English as being a formal language equivalent to a set of all texts over the English alphabet (along with symbols like space, dot, comma etc.) that we would consider to be in English as we speak it.
   8
   9 **What is this all good for?** This mathematical formalization allows us to classify languages and understand their structure, which is necessary e.g. for creating efficient compilers, but also to understand computers as such, their power and limits, as computers can be viewed as machines for processing formal languages. With these tools researches are able to come up with [proofs](proof.md) of different properties of languages, which we can exploit. For example, within formal languages, it has been proven that certain languages are uncomputable, i.e. there are some problems which a computer cannot ever solve (typical example is the [halting problem](halting_problem.md)) and so we don't have to waste time on trying to create such algorithms as we will never find any. The knowledge of formal languages can also guide us in designing computer languages: e.g. we know that regular languages are extremely simple to implement and so, if we can, we should prefer our languages to be regular.
  10
  11 ## Classification
  12
  13 We usually classify formal languages according to the **[Chomsky](chomsky.md) hierarchy**, by their computational "difficulty". Each level of the hierarchy has associated models of computation ([grammars](grammar.md), [automatons](automaton.md), expressions, ...) that are able to compute **all** languages of that level (remember that a level of the hierarchy is a superset of the levels below it and so also includes all the "simpler" languages). The hierarchy is more or less as follows:
  14
  15 - **all languages**: This includes all possible languages, even those that computers cannot analyze (e.g. the language representing the [halting problem](halting_problem.md)). These languages can only be computed by theoretical computers that cannot physically exist in our universe.
  16 - **type 0**, **recursively enumerable languages**: Most "difficult"/general languages that computers in our universe can analyze. These languages can be computed e.g. by a **[Turing machine](turing_machine.md)**, [lambda calculus](lambda_calculus.md) or a general unrestricted [grammar](grammar.md). Example language: a^n where *n* is not a [prime](prime.md).
  17 - **type 1**, **context sensitive languages**: Computed e.g. by a linearly bounded non-deterministic Turing machine or a context sensitive grammars. Example language: a^(n)b^(n)c^(n), n >= 0 (strings of *n* *a*s, followed by *n* *b*s, followed by *n* *c*s).
  18 - **type 2**, **context free languages**: Computed by e.g. non-deterministic pushdown automata or context free grammars. (Deterministic pushdown automata compute a class of languages that is between type 2 and type 3).
  19 - **type 3**, **regular languages**: The *easiest*, *weakest* kind of languages, computed e.g. by [finite state automata](finite_state_automaton.md)s or [regular expressions](regexp.md). This class includes also all finite languages.
  20
  21 Note that here we are basically always examining **[infinite](infinity.md) languages** as finite languages are trivial. If a language is finite (i.e. the set of all strings of the language is finite), it can automatically be computed by any type 3 computational model. In [real life](irl.md) computers are actually always equivalent to a finite state automaton, i.e. the *weakest* computational type (because a computer memory is always finite and so there is always a finite number of states a computer can be in). However this doesn't mean there is no point in studying infinite languages, of course, as we're still interested in the structure, computational methods and approximating the infinite models of computation.
  22
  23 Also bear in mind these classes aren't exhaustive, there exist more classes and there are still undiscovered/unproven classes of languages, the Chomsky hierarchy enumerates just the important ones. For example regular languages have a further subclass of star-free languages.
  24
  25 **NOTE**: When trying to classify a [programming language](programming_language.md), we have to be careful about what we classify: one thing is what a program written in given language can compute, and another thing is the language's [syntax](syntax.md). To the former all strict general-purpose programming languages such as [C](c.md) or [JavaScript](javascript.md) are type 0 ([Turing complete](turing_complete.md)). From the syntax point of view it's a bit more complicated and we need to further define what exactly a syntax is (where is the line between syntax and semantic errors): it may be (and often is) that syntactically the class will be lower. There is actually a famous [meme](meme.md) about [Perl](perl.md) syntax being undecidable.