Article
Article
- Computing & Information Technology
- Programming and software
- Language theory
Language theory
Article By:
Mata-Toledo, Ramon A. Department of Computer Science, Rollins College, Winter Park, Florida.
Last reviewed:January 2020
DOI:https://doi.org/10.1036/1097-8542.801220
- Types of grammars
- Acceptors, generators, and translators
- Related Primary Literature
- Additional Reading
An attempt to formulate the grammar of a language in mathematical terms. Language theory is an important area of linguistics and computer science. Formal language theory was initiated in the mid-1950s in an attempt to develop theories on natural language acquisition. This theory, and in particular context-free grammars, was found to be relevant to the languages used in computers. Interest in the relationship between abstract languages and automata theory began with a seminal paper by S. C. Kleene in 1956, in which he characterized the languages in which membership of a sentence could be decided by a finite-state machine. Formal or abstract languages are based on the mathematical notion of a language as defined by Noam Chomsky around 1956. To understand this concept, we may begin by defining what a language is. The New Oxford American Dictionary defines it as “the method of human communication, either spoken or written, consisting of the use of words in a structured and conventional way.” However, this definition is too vague to use as a building block of a language theory. To formalize the notion of an abstract language, it is necessary to introduce some preliminary definitions. An alphabet, vocabulary, or the set of terminals, denoted by Σ, is any finite, nonempty set of indivisible symbols. For example, the binary alphabet has only two symbols. This set is generally represented as Σ = {0, 1}. A word or string, over a particular alphabet, is a finite sequence of symbols of the alphabet. In mathematical terms, a typical word, x, can be written as x = a1, a2, a3, …,ak where k ≥ 0, ai ∊ Σ for 1 ≤ i ≤ k. Notice that if k = 0, the word is called the null word or empty word and is denoted by Λ. For example, using the binary alphabet we can form the words x = 0010 and y = 010. Given a word, x, the number of occurrences of symbols of a given alphabet in the word is called the length of the word and is denoted by |x|. According to this definition, the length of the words |x| = |0010| and |y| = |010| are 4 and 3, respectively. For a particular alphabet, a sentence is a finite sequence of words. See also: Automata theory; Linguistics
The content above is only an excerpt.
for your institution. Subscribe
To learn more about subscribing to AccessScience, or to request a no-risk trial of this award-winning scientific reference for your institution, fill in your information and a member of our Sales Team will contact you as soon as possible.
to your librarian. Recommend
Let your librarian know about the award-winning gateway to the most trustworthy and accurate scientific information.
About AccessScience
AccessScience provides the most accurate and trustworthy scientific information available.
Recognized as an award-winning gateway to scientific knowledge, AccessScience is an amazing online resource that contains high-quality reference material written specifically for students. Contributors include more than 10,000 highly qualified scientists and 46 Nobel Prize winners.
MORE THAN 8700 articles covering all major scientific disciplines and encompassing the McGraw-Hill Encyclopedia of Science & Technology and McGraw-Hill Yearbook of Science & Technology
115,000-PLUS definitions from the McGraw-Hill Dictionary of Scientific and Technical Terms
3000 biographies of notable scientific figures
MORE THAN 19,000 downloadable images and animations illustrating key topics
ENGAGING VIDEOS highlighting the life and work of award-winning scientists
SUGGESTIONS FOR FURTHER STUDY and additional readings to guide students to deeper understanding and research
LINKS TO CITABLE LITERATURE help students expand their knowledge using primary sources of information