Abstract
The following survey reviews some connections between formal languages and complexity theory. Families of formal languages are treated with complexity theoretical methods. In particular, the concept of unambiguity, common to both areas, is treated in detail. Some complexity theoretical aspects of operations on formal languages are indicated. This picture is completed by taking parallel models into account.
Get full access to this article
View all access options for this article.