Formal language 10939 226046107 2008-07-16T16:15:16Z Cyclonenim 1572590 Reverted edits by [[Special:Contributions/60.243.153.105|60.243.153.105]] to last version by AlleborgoBot (using [[WP:HG|Huggle]]) :''This article is about a technical term in mathematics and computer science. For related studies about natural languages, see [[grammar framework]]. For formal language as a mode of speech, see [[Register (linguistics)]].'' A '''formal language''' is a [[set (mathematics)|set]] of ''words'', i.e. finite [[string (computer science)|strings]] of ''letters'', or ''symbols''. The inventory from which these letters are taken is called the ''alphabet'' over which the language is defined. A formal language is often defined by means of a [[formal grammar]]. Formal languages are a purely [[syntax|syntactical]] notion, i.e. a priori there is no [[meaning (linguistics)|meaning]] associated with them. To distinguish the words of a language from arbitrary words over its alphabet, they are sometimes called ''well-formed words'' (or, in their application in [[logic]], [[well-formed formula]]s). Formal languages are studied in the fields of [[logic]], [[computer science]] and [[linguistics]]. Their most important practical application is for the precise definition of syntactically correct [[computer program|programs]] for a [[programming language]]. The branch of mathematics and computer science that is concerned only with the purely syntactical aspects of such languages, i.e. their internal structural patterns, is known as '''formal language theory'''. Although it is not formally part of the language, the words of a formal language often have a [[formal semantics|semantical]] dimension as well. In practice this is always tied very closely to the structure of the language, and a formal grammar (a set of formation rules that recursively defines the language) can help to deal with the meaning of (well formed) words. Well-known examples for this are "[[Alfred Tarski|Tarski's]] definition of truth" in terms of a [[T-schema]] for [[first-order logic]], and [[compiler generator]]s like [[lex programming tool|<code>lex</code>]] and <code>[[yacc]]</code>. ==Words over an alphabet== An '''alphabet''', in the context of formal languages can be any [[set (mathematics)|set]], although it often makes sense to use an [[alphabet]] in the usual sense of the word, or more generally a [[character set]] such as [[ASCII]]. Alphabets can also be infinite; e.g. [[first-order logic]] is often expressed using an alphabet which, besides symbols such as ∧, ¬, ∀ and parentheses, contains infinitely many elements ''x''<sub>0</sub>,&nbsp;''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;… that play the role of variables. The elements of an alphabet are called its '''letters'''. A '''word''' over an alphabet can be any [[tuple|finite sequence]], or [[string (computer science)|string]], of letters. The set of all words over an alphabet Σ is usually denoted by Σ<sup>*</sup>. For any alphabet there is only one word of length 0, the ''empty word'', which is often denoted by e, ε or Λ. By [[concatenation]] one can combine two words to form a new word, whose length is the sum of the lengths of the original words. The result of concatenating a word with the empty word is the original word. In some applications, especially in [[logic]], the alphabet is also known as the ''vocabulary'' and words are known as ''formulas'' or ''sentences''; this breaks the letter/word metaphor and replaces it by a word/sentence metaphor. ==Definition== A '''formal language''' ''L'' over an alphabet Σ is just a [[subset]] of Σ<sup>*</sup>, i.e. ''L''&nbsp;⊆&nbsp;Σ<sup>*</sup>. In computer science and mathematics, which do not deal with [[natural language]]s, the adjective "formal" is usually omitted as redundant. Formal language theory is most interested in formal languages that are defined by some syntactical rules, but these rules are not part of the definition, which intentionally allows arbitrary subsets of Σ<sup>*</sup>. The notion of a [[formal grammar]] is arguably closer to the intuition of what the precise definition of a "formal language" should be, and by an abuse of language a concrete formal language is often thought of as being equipped with a formal grammar that defines it. ==Examples== The following rules define a formal language ''L'' over the alphabet Σ&nbsp;=&nbsp;{''0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =''}: * Every nonempty string that does not contain ''+'' or ''='' and does not start with ''0'' is in ''L''. * The string ''0'' is in ''L''. * A string containing ''='' is in ''L'' if and only if there is exactly one ''='', and it separates two strings in ''L''. * A string containing ''+'' is in ''L'' if and only if every ''+'' in the string separates two valid strings in ''L''. * No string is in ''L'' other than those implied by the previous rules. Under these rules, the string "''23+4=555''" is in ''L'', but the string "''=234=+''" is not. This formal language expresses [[natural number]]s, well-formed addition statements, and well-formed addition equalities, but it expresses only what they look like (their [[syntax]]), not what they mean ([[semantics]]). For instance, nowhere in these rules is there any indication that ''0'' means the number zero, or that + means addition. For finite languages one can simply enumerate all well formed words. However, even over a finite (non-empty) alphabet such as Σ&nbsp;=&nbsp;{''a'',&nbsp;''b''} there are infinitely many words: "''a''", "''abb''", "''ababba''", "''aaababbbbaab''",&nbsp;…. Therefore formal languages are typically infinite, and defining a formal language is not always as simple as writing ''L''&nbsp;=&nbsp;{''"a", "b", "ab", "cba"''}. Here are some examples of formal languages: * ''L'' = Σ<sup>*</sup>, the set of ''all'' words over {''a'',&nbsp;''b''}; * ''L'' = {''a''}<sup>*</sup> = {''a<sup>n</sup>''}, where ''n'' ranges over the [[natural number]]s and ''a<sup>n</sup>'' means ''a'' repeated ''n'' times; * the set of syntactically correct programs in a given programming language; * the set of inputs upon which a certain [[Turing machine]] halts; or * the set of maximal strings of [[alphanumeric]] [[ASCII]] characters on this line, (i.e., the set {''"the", "set", "of", "maximal", "strings", "alphanumeric", "ASCII", "characters", "on", "this", "line"''}). == Language specification formalisms == Formal language theory rarely concerns itself with particular languages (except as examples), but is mainly concerned with the study of various types of formalisms to describe languages. For instance, a language can be given as * A set of strings that can be generated by some [[formal grammar]] (see [[Chomsky hierarchy]]); * A set of strings described or matched by a particular [[regular expression]]; * A set of strings accepted by some [[automaton]], such as a [[Turing machine]] or [[Finite state machine|finite state automaton]]; * A set of strings for which some [[decision problem|decision procedure]] (an [[algorithm]] that asks a sequence of related YES/NO questions) produces the answer YES. Typical questions asked about such formalisms include: * What is their expressive power? (Can formalism X describe every language that formalism Y can describe? Can it describe other languages?) * What is their recognizability? (How difficult is it to decide whether a given word belongs to a language described by formalism X?) * What is their comparability? (How difficult is it to decide whether two languages, one described in formalism X and one in formalism Y, or in X again, are actually the same language?). Surprisingly often, the answer to these decision problems is "it cannot be done at all", or "it is extremely expensive" (with a precise characterization of how expensive exactly). Therefore, formal language theory is a major application area of [[Computability theory (computer science)|computability theory]] and [[computational complexity theory|complexity theory]]. == Operations on languages == Certain operations on languages are common. This includes the standard set operations, such as union, intersection, and complementation. Another class of operation is the elementwise application of string operations. Examples: suppose ''L''<sub>1</sub> and ''L''<sub>2</sub> are languages over some common alphabet. * The ''[[concatenation]]'' ''L''<sub>1</sub>''L''<sub>2</sub> consists of all strings of the form ''vw'' where ''v'' is a string from ''L''<sub>1</sub> and ''w'' is a string from ''L''<sub>2</sub>. * The ''intersection'' ''L''<sub>1</sub>&nbsp;∩&nbsp;''L''<sub>2</sub> of ''L''<sub>1</sub> and ''L''<sub>2</sub> consists of all strings which are contained in both languages * The ''complement'' ¬''L'' of a language with respect to a given alphabet consists of all strings over the alphabet that are not in the language. Such operations are used to investigate [[closure (mathematics)|closure properties]] of classes of languages. A class of languages is [[closure (mathematics)|closed under]] a particular operation when the operation, applied to languages in the class, always produces a language in the same class again. For instance, the [[context-free language]]s are known to be closed under union, concatenation, and intersection with [[regular language]]s, but not closed under intersection or complementation. == Other operations on languages == Some other operations frequently used in the study of formal languages are the following: * The [[Kleene star]]: the language consisting of all words that are [[concatenation]]s of 0 or more words in the original language; * ''Reversal'': ** Let ''e'' be the empty word, then ''e<sup>R</sup>''&nbsp;=&nbsp;''e'', and ** for each non-empty word ''w''&nbsp;=&nbsp;''x''<sub>1</sub>…''x<sub>n</sub>'' over some alphabet, let ''w<sup>R</sup>''&nbsp;=&nbsp;''x''<sub>n</sub>…''x<sub>1</sub>'', ** then for a formal language ''L'', ''L<sup>R</sup>&nbsp;=&nbsp;{''w<sup>R</sup>&nbsp;|&nbsp;''w'' ∈ ''L''}. * [[Homomorphism]] and [[e-free homomorphism]]. == References == {{Reflist}} {{Refbegin}} * A. G. Hamilton, ''Logic for Mathematicians'', Cambridge University Press, 1978, ISBN 0 521 21838 1. * [[Seymour Ginsburg]], ''Algebraic and automata theoretic properties of formal languages'', North-Holland, 1975, ISBN 0 7204 2506 9. * Michael A. Harrison: Introduction to Formal Language Theory, Addison-Wesley, 1978. * Grzegorz Rozenberg, Arto Salomaa, ''Handbook of Formal Languages: Volume I-III'', Springer, 1997, ISBN 3 540 61486 9. * Patrick Suppes, ''Introduction to Logic'', D. Van Nostrand, 1957, ISBN 0 442 08072 7. {{Refend}} == See also == * [[Formal grammar]] * [[Grammar framework]] * [[Formal method]] * [[Formal science]] * [[Formal system]] * [[Mathematical notation]] * [[Programming language]] == External links == * {{MathWorld |title=Formal Language |urlname=FormalLanguage}} * {{planetmath reference|id=1681|title=Alphabet}} * {{planetmath reference|id=1767|title=Language}} * [[University of Maryland, Baltimore|University of Maryland]], [http://www.csee.umbc.edu/help/theory/lang_def.shtml Formal Language Definitions] * James Power, [http://www.cs.nuim.ie/~jpower/Courses/parsing/ "Notes on Formal Language Theory and Parsing"], [[29 November]] [[2002]]. * Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1-3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):t ** Alexandru Mateescu and Arto Salomaa, [http://www.cs.cmu.edu/~lkontor/noam/Mateescu-Salomaa.pdf "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39] ** Sheng Yu, [http://www.csd.uwo.ca/~syu/public/draft.ps "Regular Languages", Chapter 2 in Vol. 1] ** Jean-Michel Autebert, Jean Berstel, Luc Boasson, [http://citeseer.ist.psu.edu/248295.html "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1] ** Christian Choffrut and Juhani Karhumäki, [http://www.liafa.jussieu.fr/~cc/PUBLICATIONS/CKTUCS.PS.gz "Combinatorics of Words", Chapter 6 in Vol. 1] ** Tero Harju and Juhani Karhumäki, [http://users.utu.fi/harju/articles/morph.pdf "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510] ** Jean-Eric Pin, [http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746] ** M. Crochemore and C. Hancart, [http://www-igm.univ-mlv.fr/~mac/REC/DOC/B4.ps "Automata for matching patterns", Chapter 9 in Vol. 2] ** Dora Giammarresi, Antonio Restivo, [http://bruno.maitresdumonde.com/optinfo/Spe-MP/dmds1998/2dlang/giammaresi-restivo-paper.ps "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267] {{logic}} [[Category:Formal languages]] [[ar:لغة شكلية]] [[bs:Formalni jezik]] [[bg:Формален език]] [[cs:Formální jazyk]] [[da:Formelt sprog]] [[de:Formale Sprache]] [[el:Τυπική γλώσσα]] [[es:Lenguaje formal]] [[fa:زبان‌های فرمال]] [[fr:Langage formel]] [[ko:형식 언어]] [[hi:औपचारिक भाषा]] [[hr:Formalni jezik]] [[it:Linguaggio formale (matematica)]] [[he:שפה פורמלית]] [[hu:Formális nyelv]] [[mk:Формален јазик]] [[nl:Formele taal]] [[ja:形式言語]] [[pl:Język formalny]] [[pt:Linguagem formal]] [[ro:Limbaje formale]] [[ru:Формальный язык]] [[simple:Formal language]] [[sk:Formálny jazyk]] [[fi:Formaali kieli]] [[tr:Biçimsel dil kuramı]] [[uk:Формальна мова]] [[zh:形式语言]]