Formal Languages
In computability theory in computer science, it is common to consider formal languages. An alphabet is an arbitrary set. A word on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet {0, 1} . A language is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones is a language over the binary alphabet.
A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called computable (synonyms: recursive, decidable) if there is a computable function f such that for each word w over the alphabet, f(w) = 1 if the word is in the language and f(w) = 0 if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.
A language is computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that f(w) is defined if and only if the word w is in the language. The term enumerable has the same etymology as in computably enumerable sets of natural numbers.
Read more about this topic: Computable Function
Famous quotes containing the words formal and/or languages:
“The manifestation of poetry in external life is formal perfection. True sentiment grows within, and art must represent internal phenomena externally.”
—Franz Grillparzer (1791–1872)
“Science and technology multiply around us. To an increasing extent they dictate the languages in which we speak and think. Either we use those languages, or we remain mute.”
—J.G. (James Graham)