Language class

In linguistics and computer science, a language class is a set of languages ​​that can be formed using a given alphabet . A language is a set of words above this alphabet, and an alphabet is a (usually finite) set of characters or symbols.

The American publicist and language theorist Noam Chomsky divided the languages that intelligent beings can recognize or classify into four abstract classes, thus laying the formal foundations for theoretical computer science and making a significant contribution to mathematical logic. The basis of the classification of languages ​​is a replacement and a correspondence principle, which leads to the classes CH (0) to CH (3). These formal language classes include mathematical logic , mathematical algebra, and all other man-made calculi.

Language classes can be defined by specifying formal grammars , by automata or by applying operations to (already known) language classes. They have their counterparts in the machine models , similar to how software relates to hardware.

Well-known language classes are:

• 3 - the set of regular languages .
• 2 - the set of context-free languages
• 1 - the set of context-sensitive languages
• 0 - the set of recursively enumerable languages
•   - the set of all languages

See also

• Chomsky hierarchy

literature

• Werner Ebinger: Characterization of language classes with infinite traces through logics . Diss., University of Stuttgart, 1994.