Four language classes sit inside one another: regular, context-free, context-sensitive and recursively enumerable. Each class has a type of grammar that generates it and a kind of machine that recognizes it, and every step outward adds expressive power. The sections below follow that ladder from the bottom, starting with what the field is about and ending with the point where grammars meet real parsers and data formats.
What does the theory of computation study?
The theory of computation asks what problems can be solved on a model of computation using an algorithm, and how efficiently they can be solved. It is not tied to one programming language or one processor. The models are deliberately small, so that statements about them can be proved: a machine with a fixed number of states, a machine with a stack, a machine with an unbounded tape.
The field is usually divided into three branches. Automata theory and formal languages studies abstract machines and the sets of strings they accept. Computability theory asks which problems can be solved by any algorithm at all. Complexity theory asks how much time or memory the solvable ones need. University courses in the subject follow the same split, for example the MIT course that is organized into automata and language theory, computability theory and complexity theory. A shared question runs through all three: what are the fundamental capabilities and limitations of computers?
This page covers the first branch. It introduces the four language classes, shows what each can and cannot express, and points to detailed pages on automata, grammars and proofs.
What is a formal language, and what is a grammar?
An alphabet is a finite set of symbols, such as {0, 1} or the letters a and b. A string, also called a word, is a finite sequence of those symbols. A formal language is a set of strings over an alphabet, and nothing more: the strings that end in 1 form a language, and so do the strings with equally many a and b.
A grammar generates a language. It starts from a start symbol and applies rewriting rules until only symbols of the alphabet remain; the strings that can be reached this way make up the language. An automaton works in the opposite direction, because it reads a given string and decides whether it belongs to the language. A parser goes one step further: besides accepting or rejecting, it builds a structure, usually a tree, that shows how the string is put together.
These roles are easy to blur, so the distinction matters. Recognizing a string is not the same as interpreting it. Two different grammars can also describe the same language while producing different trees, which is why the language and the grammar that happens to describe it are kept apart.
What does it mean for a language to be regular?
A language is regular when a finite automaton recognizes it. The same class can be described in two further ways: by a regular expression and by a regular grammar. All three descriptions are interchangeable, which is what makes the class so well behaved. In a regular grammar every rule has a very restricted shape. In the right-linear variant used here, a rule is of the form A → a or A → aB, with a single terminal symbol and at most one nonterminal after it, and many definitions also allow a rule that produces the empty string. Textbooks differ in these details, and both left-linear and right-linear grammars give regular languages. The page on left-linear and right-linear grammars compares the two forms and shows how to convert one into the other.
A small example shows the shape. Over the alphabet {0, 1}, the rules S → 0S, S → 1S and S → 1 generate every string that ends in 1: the grammar keeps writing symbols and may stop only by writing a final 1. A two-state automaton recognizes the same language, and that pairing of grammar and machine is the pattern repeated at every level of the hierarchy.
Regular languages cover tokens, identifiers, numbers with a fixed format and flat record fragments. Their weakness is memory. A finite automaton has a fixed number of states and no other storage, so it cannot enforce unbounded nesting and cannot match one count against another. Whenever a format asks for balanced brackets or for as many closing tags as opening ones, it leaves the regular class.
Because the three descriptions agree, any of them can be used to reason about the others. A property proved with automata, for instance, carries over to regular expressions and regular grammars without further work.
Which language does a finite automaton accept?
A finite automaton accepts exactly the regular languages. There are two common kinds. A deterministic finite automaton, or DFA, has exactly one move for each state and input symbol. A nondeterministic finite automaton, or NFA, may have several moves for the same symbol, or none, and accepts a string if at least one sequence of moves ends in an accepting state.
| Machine | Moves per symbol | Accepts a string when | Language class |
|---|---|---|---|
| DFA | exactly one | the single run ends in an accepting state | regular |
| NFA | zero, one or several | at least one run ends in an accepting state | regular |
Every DFA can be read as an NFA, so the nondeterministic machine is at least as general. Rabin and Scott showed in 1959 that it is not more powerful: every NFA has a DFA that accepts the same language. The nondeterministic version can still be much shorter to write down. The details are on the page about nondeterministic finite automata, and the construction that removes the nondeterminism is described under converting an NFA to a DFA.
How do regular expressions relate to regular languages?
A regular expression is a notation for a set of strings built from single symbols, concatenation, alternatives and repetition. In the formal sense, regular expressions describe exactly the regular languages, which is why they suit search patterns and the lexical structure of programming languages.
Practical regex engines are a different matter. Many add features such as backreferences, and a pattern that requires the same substring to appear twice describes a language that is not regular. A pattern that repeats a captured group, for example, matches exactly the strings that consist of a word written twice in a row. An engine with such features therefore goes beyond the regular class, and what it can do should not be inferred from the formal name alone.
What is an example of a non-regular language?
The standard example is the set of strings anbn: some number of a symbols followed by the same number of b symbols, such as ab, aabb and aaabbb. This language is context-free but not regular.
The intuition is a counting argument, and it explains why this language marks the edge of the regular class. To accept anbn an automaton must remember how many a symbols it has read, and n can be larger than any fixed number of states. Once two different counts lead to the same state, the machine can no longer tell them apart. That is only an explanation; a proof needs the pumping lemma, which turns the idea into a precise statement about long strings in a regular language. The pumping lemma page carries out that proof for anbn step by step.
How do context-free grammars go beyond regular ones?
A context-free grammar allows a single nonterminal on the left of a rule and anything on the right, including the same nonterminal. That recursion is what produces nesting. The rules S → aSb and S → ε generate anbn: the derivation S ⇒ aSb ⇒ aaSbb ⇒ aabb produces the string aabb, and each extra application of the first rule adds one a on the left and one b on the right. The same idea handles balanced parentheses, nested expressions and nested markup.
The matching machine is the pushdown automaton, a finite automaton with a stack. The stack supplies exactly the memory that a plain finite automaton lacks, so it can count a symbols and compare them with the b symbols that follow.
Context-free grammars bring a problem that regular ones do not have, namely ambiguity. A grammar is ambiguous when some string has more than one parse tree. That may be harmless when only recognition matters, but it is dangerous when the tree drives evaluation, because two trees can mean two different results. Precedence rules or a rewritten grammar settle the question. Grammars are also rewritten into normal forms for proofs and algorithms, and the Greibach normal form page shows one such rewriting in full.
How does the Chomsky hierarchy order the language classes?
The Chomsky hierarchy sorts grammars into four types, numbered 3 to 0, and each type generates a class of languages that a particular machine recognizes. The classes are nested: every regular language is context-free, every context-free language is context-sensitive, and every context-sensitive language is recursively enumerable. All three inclusions are strict, so each larger class contains languages that the smaller one cannot express.
| Type | Language class | Rule shape | Machine | Example language |
|---|---|---|---|---|
| 3 | Regular | A → a or A → aB | Finite automaton | Strings that end in 1 |
| 2 | Context-free | A → γ, one nonterminal on the left | Nondeterministic pushdown automaton | anbn |
| 1 | Context-sensitive | αAβ → αγβ, with γ not empty | Linear bounded automaton | anbncn |
| 0 | Recursively enumerable | unrestricted rules | Turing machine | Descriptions of Turing machines that halt |
The examples mark the boundaries. Strings that end in 1 need only a finite automaton. The language anbn needs a stack. The language anbncn, with three matching counts, is context-sensitive but not context-free. At the top, the set of descriptions of Turing machines that halt is recursively enumerable, the class recognized by a Turing machine.
A higher type is more expressive, but that does not make it the better engineering choice. Recognition gets more expensive, tools get scarcer and error messages get worse as the class grows. The usual advice for a data format is therefore to pick the simplest class that captures the syntax and to check context-dependent rules in a separate step that can explain failures clearly.
Where do grammars meet parsers and data formats?
Parser strategies
A top-down parser starts at the start symbol and predicts which rule to apply, while a bottom-up parser combines recognized pieces until it reaches the start symbol. LL parsers work top-down and LR parsers work bottom-up. The choice depends on the grammar, on how much error recovery is needed and on the tools at hand, not on a universal ranking.
Data formats need more than a grammar
A grammar locates structure, but an interoperable format also settles character encoding, number representation, length limits and meaning. A sample that happens to parse does not prove that a parser follows the format.
Testing language processors
Test sets should hold both valid and invalid input around every boundary: empty input, the shortest productions, maximum nesting and unexpected end of input. A test verifies acceptance and also the tree that comes out. Small hand-checked examples protect the intended language when a grammar is refactored.
Grammar transformations belong in the same picture. Removing left recursion or converting to a normal form supports proofs and particular algorithms, but it can make a grammar harder to read and change the shape of its parse trees even though the language stays the same.
Continue with a working reference
- Nondeterministic finite automata, with a step-through run
- NFA to DFA conversion, the subset construction
- Pumping lemma, for proving that a language is not regular
- Left-linear to right-linear grammar
- Greibach normal form
Frequently asked questions
01What is the meaning of regex?
Regex is short for regular expression, a compact notation for describing a set of strings. In the formal sense a regular expression describes exactly the regular languages. Many practical regex engines add features such as backreferences that reach beyond that class.
02Why learn the theory of computation?
The subject studies the fundamental capabilities and limits of computers. It explains which problems a machine can solve at all, which kinds of structure a simple machine can and cannot recognize, and why some tasks need more powerful models than others.