Formal language

In mathematics, logic and computer science, a formal language is a set of finite-length words (i.e. character strings) drawn from some finite alphabet. Note that we can talk about formal language in many contexts (scientific, legal and so on), meaning a mode of expression more careful and accurate than everyday speech. Use of a particular formal language in the sense intended here is an 'ultimate' version of that usage: formal enough to be used in written form for automatic computation, is a possible criterion. A typical alphabet would be {a, b}, and a typical string over that alphabet would be

ababba.

A typical language over that alphabet, containing that string, would be the set of all strings which contain the same number of symbols a and b. The empty word (that is, length-zero string) is allowed and is often denoted by e, ε or λ. While the alphabet is a finite set and every string has finite length, a language may very well have infinitely many member strings (because the length of words in it may be unbounded). Some examples of formal languages:

• the set of all words over {a, b};\n* the set { aⁿ : n is a prime number };\n* the set of syntactically correct programs in a given programming language; or\n* the set of inputs upon which a certain Turing machine halts.

A formal language can be specified in a great variety of ways, such as:

• Strings produced by some formal grammar (see Chomsky hierarchy);\n* Strings produced by a regular expression;\n* Strings accepted by some automaton, such as a Turing machine or finite state automaton; \n* From a set of related YES/NO questions those ones for which the answer is YES — see decision problem.

Several operations can be used to produce new languages from given ones. Suppose L₁ and L₂ are languages over some common alphabet.\n* The concatenation L₁L₂ consists of all strings of the form vw where v is a string from L₁ and w is a string from L₂.\n* The intersection of L₁ and L₂ consists of all strings which are contained in L₁ and also in L₂.\n* The union of L₁ and L₂ consists of all strings which are contained in L₁ or in L₂.\n* The complement of the language L₁ consists of all strings over the alphabet which are not contained in L₁.\n* The right quotient L₁/L₂ of L₁ by L₂ consists of all strings v for which there exists a string w in L₂ such that vw is in L₁.\n* The Kleene star L₁* consists of all strings which can be written in the form w₁w₂...w_n with strings w_i in L₁ and n ≥ 0. Note that this includes the empty string ε because n = 0 is allowed.\n* The reverse L₁^R contains the reversed versions of all the strings in L₁.\n* The shuffle of L₁ and L₂ consists of all strings which can be written in the form v₁w₁v₂w₂...v_nw_n where n ≥ 1 and v₁,...,v_n are strings such that the concatenation v₁...v_n is in L₁ and w₁,...,w_n are strings such that w₁...w_n is in L₂. A typical question asked about a formal language is how difficult it is to decide whether a given word belongs to the language.\nThis is the domain of computability theory and complexity theory. \n\n\n\n\nzh-cn:形式语言\nzh-tw:形式語言 Category:Formal languages