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.
 •
 •
 •

•
derivation^{}
 •
 •

•
isomorphism^{} of languages

•
language
 •

•
reversal or mirror image

•
initial symbol

•
production
 •
 •

•
syntax

•
terminal symbol

•
nonterminal symbol

•
word
2 Classification of languages
 •
 •
 •
 •

•
phrasestructure language

•
type3 language

•
type2 language

•
type1 language

•
type0 language
3 Regular (type 3) languages
 •
 •
 •

•
leftlinear grammar

•
rightlinear grammar

•
finite automaton
4 Contextfree (type 2) languages
 •
 •

•
intersection^{} of contextfree and regular languages is contextfree
 •

•
rightmost derivation
 •
 •
 •
 •

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

•
Earley’s algorithm^{}
 •

•
$LL(k)$ (http://planetmath.org/LLk) grammar

•
leftfactored grammar

•
$LR(k)$ (http://planetmath.org/LRk) 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

•
finitely presented group
 •

•
semiThue system (http://planetmath.org/SemiThueSystem)
 •
 •
 •

•
conjugacy problem
9 Decidability

•
membership problem

•
emptiness problem

•
recursively enumerable language

•
recursive language
10 Special languages
 •
 •
Title  theory of formal languages 
Canonical name  TheoryOfFormalLanguages 
Date of creation  20130322 15:06:37 
Last modified on  20130322 15:06:37 
Owner  rspuzio (6075) 
Last modified by  rspuzio (6075) 
Numerical id  16 
Author  rspuzio (6075) 
Entry type  Topic 
Classification  msc 68R15 
Classification  msc 68Q70 
Classification  msc 68Q45 
Classification  msc 68Q42 
Classification  msc 20M05 
Classification  msc 20F10 
Classification  msc 08A50 
Classification  msc 03D40 
Classification  msc 03D05 
Classification  msc 03C07 