# Article

# Article

- Computing & Information Technology
- Programming and software
- Language theory

# Language theory

Article By:

**Mata-Toledo, Ramon A. **Department of Computer Science, James Madison University, Harrisonburg, Virginia.

Last updated:2014

DOI:https://doi.org/10.1036/1097-8542.801220

- Types of grammars
- Acceptors, generators, and translators

- Links to Primary Literature

- Additional Readings

**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 = a_{1}, a_{2}, a_{3}, …,a_{k} where k ≥ 0, a_{i} ∊ Σ 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. Its dedicated editorial team is led by Sagan Award winner John Rennie. Contributors include more than 9000 highly qualified scientists and 42 Nobel Prize winners.

**MORE THAN 8500** articles and Research Reviews 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 17,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