https://tcs.nju.edu.cn/wiki/api.php?action=feedcontributions&feedformat=atom&user=61.6.239.245TCS Wiki - User contributions [en]2026-05-02T18:53:35ZUser contributionsMediaWiki 1.45.3https://tcs.nju.edu.cn/wiki/index.php?title=Formal_language&diff=7553Formal language2017-02-25T00:57:20Z<p>61.6.239.245: Fixed typo, Fixed grammar, Added links</p>
<hr />
<div>Language<br />
<br />
== Examples ==<br />
<br />
Some examples of formal languages:<br />
<br />
* the set of all words over <math>{a, b}\,</math><br />
* the set <math>\left \{ a^{n}\right\}</math>, where <math>n\,</math> is a [[natural number]] and <math>a^n\,</math> means <math>a\,</math> repeated <math>n\,</math> times<br />
* finite languages, such as <math>\{\{a,b\},\{a, aa, bba\}\}\,</math><br />
* the set of syntactically correct programs in a given programming language; or<br />
* the set of inputs upon which a certain [[Turing machine]] halts.<br />
<br />
== Specification ==<br />
<br />
A formal language can be specified in a great variety of ways, such as:<br />
<br />
* Strings produced by some [[formal grammar]] (see [[Chomsky hierarchy]]);<br />
* Strings described or matched by a [[regular expression]];<br />
* Strings accepted by some [[automaton]], such as a [[Turing machine]] or [[Finite state machine|finite state automaton]];<br />
* Strings indicated by a [[decision problem|decision procedure]] (a set of related YES/NO questions) where the answer is YES.<br />
<br />
<!--<br />
==Operations==<br />
Several operations can be used to produce new languages from given ones. Suppose <math>\boldsymbol{L}_{1}</math> and <math>\boldsymbol{L}_{2}</math> are languages over some common alphabet.<br />
* The ''[[concatenation]]'' <math>\boldsymbol{L}_{1}\boldsymbol{L}_{2}\,</math> consists of all strings of the form <math>vw\,</math> where <math>v\,</math> is a string from <math>\boldsymbol{L}_{1}\,</math> and <math>w\,</math> is a string from <math>\boldsymbol{L}_{2}\,</math>.<br />
* The ''intersection'' <math>\boldsymbol{L}_1 \cap \boldsymbol{L}_2</math> of <math>\boldsymbol{L}_{1}\,</math> and <math>\boldsymbol{L}_{2}\,</math> consists of all strings which are contained in <math>\boldsymbol{L}_{1}\,</math> and also in <math>\boldsymbol{L}_{2}\,</math>.<br />
* The ''union'' <math>\boldsymbol{L}_1 \cup \boldsymbol{L}_2</math> of <math>\boldsymbol{L}_{1}\,</math> and <math>\boldsymbol{L}_{2}\,</math> consists of all strings which are contained in <math>\boldsymbol{L}_{1}\,</math> or in <math>\boldsymbol{L}_{2}\,</math>.<br />
* The ''complement'' <math>\complement \boldsymbol{L}_{1}\,</math> of the language <math>\boldsymbol{L}_{1}\,</math> consists of all strings over the alphabet which are not contained in <math>\boldsymbol{L}_{1}\,</math>.<br />
* The ''right quotient'' <math>\boldsymbol{L}_{1}/\boldsymbol{L}_{2}\,</math> of <math>\boldsymbol{L}_{1}\,</math> by <math>\boldsymbol{L}_{2}\,</math> consists of all strings <math>v\,</math> for which there exists a string <math>w\,</math> in <math>\boldsymbol{L}_{2}\,</math> such that <math>vw\,</math> is in <math>\boldsymbol{L}_{1}</math>.<br />
* The ''[[Kleene star]]'' <math>\boldsymbol{L}_{1}^{*}</math> consists of all strings which can be written in the form <math>w_{1}w_{2}...w_{n}\,</math> with strings <math>w_{i}\,</math> in <math>\boldsymbol{L}_{1}\,</math> and <math>n \ge 0</math>. Note that this includes the empty string <math>\epsilon\,</math> because <math>n = 0\,</math> is allowed.<br />
* The ''reverse'' <math>\boldsymbol{L}_{1}^{R}\,</math> contains the reversed versions of all the strings in <math>\boldsymbol{L}_{1}\,</math>.<br />
* The ''shuffle'' of <math>\boldsymbol{L}_{1}\,</math> and <math>\boldsymbol{L}_{2}\,</math> consists of all strings which can be written in the form <math>v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}</math> where <math>n \ge 1</math> and <math>v_{1},\dots,v_{n}\,</math> are strings such that the concatenation <math>v_{1}\dots v_{n}</math> is in <math>\boldsymbol{L}_{1}\,</math> and <math>w_{1},\dots,w_{n}</math> are strings such that <math>w_{1}\dots w_{n}</math> is in <math>\boldsymbol{L}_{2}</math>.<br />
--><br />
== Other pages ==<br />
* [[Language]] for languages in general<br />
* [[Syntax]] for the form of a language in general<br />
* [[Semantics]] for the meanings in a language<br />
* [[Natural language]] for languages that are not formal<br />
* [[Computer language]] for application of formal languages in computing<br />
* [[Programming language]] for the application of formal languages to program computers<br />
<br />
== Further reading ==<br />
* {{cite book<br />
| author = Hopcroft, J. & Ullman, J.<br />
| title = Introduction to Automata Theory, Languages, and Computation <br />
| publisher = Addison-Wesley<br />
| year = 1979<br />
| isbn=0-201-02988-X}}<br />
* {{cite book<br />
| author = Helena Rasiowa and Roman Sikorski<br />
| title = The Mathematics of Metamathematics<br />
| publisher = PWN<br />
| year = 1970<br />
| edition = 3<sup>rd</sup> ed.}}, chapter 6 ''Algebra of formalized languages''.<br />
* {{cite book<br />
| author = Rozemberg, G. & Salomaa, A. (eds.)<br />
| title = Introduction to Automata Theory, Languages, and Computation <br />
| publisher = Addison-Wesley<br />
| year = 1979<br />
| isbn=978-3-540-61486-9}}<br />
<br />
== Other websites ==<br />
* http://icalp06.dsi.unive.it/ ICALP 2006 33rd International Colloquium on Automata, Languages and Programming.<br />
* http://www.cs.auckland.ac.nz/CDMTCS/conferences/dlt/DLTConfSeries.html International Conferences on Developments in Language Theory<br />
<br />
[[Category:Mathematics]]<br />
[[Category:Programming languages]]</div>61.6.239.245