You are here
Hometheory of formal languages
Primary tabs
theory of formal languages
Note: This entry is very rough at the moment, and requires work. I mainly wrote it to help motivate other entries and to organize entries on this topic and point out holes in our coverage. Right now, it is mainly a list of entries, many of which have not been written yet. Under the first heading, there is short paragraph. Eventually, there should be such a paragraph under each entry and a bibliography at the end. However, this is a lot of work for one person, so this entry is world editable in the hope that others who are knowledgable in this topic will contribute their expertise.
1 Basic concepts and terminology
Loosely speaking, a formal language is a language whose structrure can be specified with mathematical precision. The study of formal languages is not only interesting as a mathematical discipline in its own right, but also because of its relevance to the foundations of mathematics, its applications, and surprising connections with other branches of mathematics.

isomorphism of languages

language

nonterminal symbol
2 Classification of languages
3 Regular (type 3) languages

leftlinear grammar

rightlinear grammar

finite automaton
4 Contextfree (type 2) languages

intersection of contextfree and regular languages is contextfree

a language is contextfree iff it can be recognized by a pushdown automaton

Earley’s algorithm

$LL(k)$ grammar

leftfactored grammar

$LR(k)$ grammar

every $LR(k)$ grammar can be recognized by a deterministic pushdown automaton

every language which can be recognized by a deterministic pushdown automaton can be described by an $LR(1)$ grammar
5 Contextsensitive (type 1) languages

lengthincreasing grammar

a language is contextsensitive iff it can be generated by a lengthincreasing grammar

a language is contextsensitive iff it can be recognized by a linear bounded automaton
6 Phrasestructure (type 0) languages

recursively enumerable language, corecursively enumerable language

language that is neither recursively enumerable, nor corecursively enumerable

every phrasestructure language is recursively enumerable
7 Other types of languages and automata that describe them

starfree language versus aperiodic finite automaton

a starfree language is regular, but not conversely

mildly contextsensitive language versus embedded pushdown automaton

treeadjoining grammar

languages generated by treeadjoining grammars are exactly the mildly contextsensitive languages

a contextfree language is mildly contextsensitive, but not conversely

indexed language versus nested stack automaton

a mildly contextsensitive language is indexed, but not conversely

an indexed language is contextsensitive, but not conversely
8 Connection to group and semigroup theory
9 Decidability

membership problem

emptiness problem

recursively enumerable language

recursive language
10 Special languages
Mathematics Subject Classification
68R15 no label found68Q70 no label found68Q45 no label found68Q42 no label found20M05 no label found20F10 no label found08A50 no label found03D40 no label found03D05 no label found03C07 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections