# 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

• reversal or mirror image

• initial symbol

• production

• syntax

• terminal symbol

• non-terminal symbol

• word

## 2 Classification of languages

• phrase-structure language

• type-3 language

• type-2 language

• type-1 language

• type-0 language

## 3 Regular (type 3) languages

• left-linear grammar

• right-linear grammar

• finite automaton

## 4 Context-free (type 2) languages

• intersection of context-free and regular languages is context-free

• rightmost derivation

• a language is context-free iff it can be recognized by a pushdown automaton

• Earley’s algorithm

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

• left-factored 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 Context-sensitive (type 1) languages

• length-increasing grammar

• a language is context-sensitive iff it can be generated by a length-increasing grammar

• a language is context-sensitive iff it can be recognized by a linear bounded automaton

## 6 Phrase-structure (type 0) languages

• recursively enumerable language, co-recursively enumerable language

• language that is neither recursively enumerable, nor co-recursively enumerable

• every phrase-structure language is recursively enumerable

## 7 Other types of languages and automata that describe them

• star-free language versus aperiodic finite automaton

• a star-free language is regular, but not conversely

• mildly context-sensitive language versus embedded pushdown automaton

• languages generated by tree-adjoining grammars are exactly the mildly context-sensitive languages

• a context-free language is mildly context-sensitive, but not conversely

• indexed language versus nested stack automaton

• a mildly context-sensitive language is indexed, but not conversely

• an indexed language is context-sensitive, but not conversely

## 8 Connection to group and semigroup theory

• finitely presented group

• semi-Thue 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 2013-03-22 15:06:37 Last modified on 2013-03-22 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