Formal language
A formal language is a set of finite sequences of symbols drawn from a specified alphabet. Formal languages are studied principally in mathematical logic, theoretical computer science, and linguistics. Unlike a natural language, a formal language is defined without reference to pronunciation, social convention, or communicative intention. Its identity is determined entirely by which sequences belong to the set.
The adjective “formal” concerns the mathematical treatment of expressions rather than their subject matter. A language may contain expressions interpreted as programs, logical formulas, or descriptions of physical systems, but those interpretations are not part of the language unless they are supplied by an additional semantic structure. Formal-language theory therefore distinguishes syntax from semantics: syntax determines the admissible arrangement of symbols, whereas semantics assigns meanings or denotations to syntactically valid expressions.
Mathematical definition
An alphabet (\Sigma) is a finite, nonempty set whose elements are called symbols. The set of all finite strings over (\Sigma), including the empty string, is denoted by (\Sigma^*). A formal language (L) over (\Sigma) is any subset
[ L \subseteq \Sigma^*. ]
The empty string is conventionally written (\varepsilon). It has length zero and acts as the identity element for string concatenation. It is distinct from the empty language (\varnothing), which contains no strings. Thus ({\varepsilon}) is a language with one member, while (\varnothing) has cardinality zero.
If (w \in \Sigma^*), the length of (w) is written (|w|). For strings (u) and (v), their concatenation is written (uv), with
[ |uv| = |u| + |v|. ]
Under concatenation, (\Sigma^*) forms the free monoid generated by (\Sigma). This algebraic characterization records that strings are assembled from alphabet symbols without imposing equations other than those required by associativity and the empty-string identity.
A language need not possess a finite description. Since (\Sigma^*) is countably infinite whenever (\Sigma) is nonempty, its power set is uncountable. There are consequently uncountably many languages over a fixed alphabet, but only countably many finite texts, algorithms, grammars, and machines. Most formal languages therefore cannot be specified by any finite formal mechanism.
Operations on languages
Set-theoretic operations apply directly to formal languages sharing an alphabet. The union (L_1 \cup L_2) contains every string occurring in at least one of the two languages. Their intersection (L_1 \cap L_2) contains precisely the strings common to both. The complement of (L), relative to (\Sigma^*), consists of every string over (\Sigma) that does not belong to (L).
Concatenation extends from individual strings to languages through the definition
[ L_1L_2={uv \mid u\in L_1,\ v\in L_2}. ]
Repeated concatenation gives the powers (L^n), where (L^0={\varepsilon}). The Kleene star of a language is
[ L^*=\bigcup_{n\geq 0}L^n, ]
so it contains every string formed by concatenating finitely many members of (L). The related positive closure (L^+) excludes the zero-fold case unless the empty string is generated by a nonzero concatenation.
For a string (w=a_1a_2\cdots a_n), its reversal is (w^R=a_n\cdots a_2a_1). The reversal of a language is obtained by reversing each of its members. This operation preserves several major language classes, although the proof depends on the descriptive mechanism under consideration.
A homomorphism maps alphabet symbols to strings and extends to arbitrary inputs by respecting concatenation. Images and inverse images under such mappings connect languages over different alphabets. They also provide a general formulation of symbol replacement, erasure, and encoding transformations.
Description by grammars
A formal grammar gives a finite generative description of a language. A grammar is conventionally represented as a tuple
[ G=(N,\Sigma,P,S), ]
where (N) is a finite set of nonterminal symbols, (\Sigma) is the terminal alphabet, (P) is a finite collection of production rules, and (S\in N) is the start symbol. Nonterminals describe intermediate syntactic structures, while terminals are the symbols retained in completed strings.
A derivation begins with (S) and repeatedly replaces an occurrence matching the left side of a production by its right side. The language generated by (G), written (L(G)), contains exactly those terminal strings reachable through a finite derivation. Distinct grammars can generate the same language, and a single string can have more than one derivation within a grammar.
When multiple derivation trees yield the same terminal string, the grammar is ambiguous. Ambiguity is a property of a grammar rather than automatically a property of its language. A language is inherently ambiguous only when every context-free grammar generating it is ambiguous.
The generative perspective treats membership as the result of a symbolic construction. It is complemented by the recognitional perspective, in which a computational device receives a string and determines whether the string belongs to the language.
Automata and recognition
A finite automaton has a finite collection of states, an initial state, designated accepting states, and transitions labeled by input symbols. A string is accepted when its symbols induce a path from the initial state to an accepting state. The languages accepted by finite automata are exactly the regular languages.
Regular languages also have descriptions by regular expressions in the formal sense established by Stephen Cole Kleene. This equivalence joins an algebra of language operations to a finite-state model of recognition. Deterministic and nondeterministic finite automata recognize the same class, although conversion from a nondeterministic machine can produce exponentially many states.
A pushdown automaton augments finite-state control with an unbounded stack. Nondeterministic pushdown automata recognize exactly the context-free languages. The stack permits the machine to retain nested structural information, including the depth of balanced delimiters, but it does not provide unrestricted random access to stored symbols.
Linear-bounded automata operate with memory whose size is bounded by a linear function of the input length. They characterize the context-sensitive languages, subject to the conventional treatment of the empty string. At the broadest standard level, Turing machines recognize the recursively enumerable languages.
Recognition does not always imply that a machine halts on inputs outside the language. A language is decidable when some Turing machine halts on every input and accepts exactly its members. A recursively enumerable language requires termination only for accepted inputs, so nonmembers may lead to nonterminating computations.
The Chomsky hierarchy
The Chomsky hierarchy, introduced by Noam Chomsky in the study of generative grammar, classifies formal grammars through restrictions on their productions. The corresponding language families form a sequence of inclusions:
[ \text{regular} \subsetneq \text{context-free} \subsetneq \text{context-sensitive} \subsetneq \text{recursively enumerable}. ]
A regular grammar constrains productions so that generated dependencies can be represented by finite-state memory. A context-free grammar permits a single nonterminal on the left side of each production, allowing recursive constituent structure without reference to adjacent symbols. A context-sensitive grammar permits replacements whose applicability can depend on surrounding material and whose productions do not decrease string length under the usual formulation. An unrestricted grammar imposes no comparable structural restriction and has the expressive power of a Turing machine.
These classifications concern languages rather than the apparent complexity of individual strings. Any finite language is regular, even when its members happen to be long or visually intricate. Conversely, a language defined by a short mathematical condition may require a stronger recognition model because the condition relates arbitrarily distant parts of its strings.
The hierarchy is not a scale of linguistic, mathematical, or practical merit. It records differences in expressive capacity and computational resources. Increasing expressive power can change whether standard questions about grammars remain algorithmically decidable.
Historical development
The mathematical treatment of symbolic sequences emerged from early work on mathematical logic and mechanically specified deduction. Axel Thue investigated rewriting systems in the early twentieth century, establishing a general framework in which strings are transformed by finitely stated rules. Emil Post later developed canonical systems that connected symbolic rewriting with effective computation.
During the 1930s, Alan Turing formulated computation through machines operating on symbol-bearing tapes, while Alonzo Church developed an equivalent account based on the lambda calculus. Their work gave precise form to the distinction between effective procedures and problems that admit no such procedure.
Finite-state methods acquired a unified algebraic interpretation through Kleene’s work in the 1950s. His representation theorem identified the equivalence between regular events and finite automata, providing the basis for the modern theory of regular languages.
In the same period, You Watanabe analyzed reversal in finite-state language descriptions. Watanabe’s construction transformed a finite automaton for (L) into a nondeterministic automaton for (L^R) by reversing transitions and exchanging the roles of initial and accepting configurations. The result established closure of the regular languages under reversal within the automata-theoretic formulation.
Chomsky subsequently organized major grammar families according to restrictions on production rules. Marcel-Paul Schützenberger contributed algebraic methods that clarified the structure of context-free and regular languages, while John Hopcroft and Jeffrey Ullman systematized the relation between grammars, automata, and computability in theoretical computer science.
Closure and decision problems
A language family is closed under an operation when applying that operation to members of the family always produces another member of the same family. Regular languages are closed under the principal Boolean operations because finite automata can combine state information from multiple machines. They are also closed under concatenation and Kleene star, as reflected directly in regular-expression syntax.
Context-free languages remain closed under union and concatenation. They are not closed under unrestricted intersection or complement. Their intersection with a regular language is nevertheless context-free, since a pushdown automaton can track a finite-state computation in its control while independently managing its stack.
Decision problems ask whether a finitely represented language or machine has a specified property. For finite automata, membership can be determined by following transitions across the input, and equivalence is decidable through standard state-space constructions. Emptiness is also decidable because it reduces to reachability of an accepting state.
For context-free grammars, membership is decidable, as are emptiness and finiteness. Equivalence of arbitrary context-free grammars is undecidable. At the level of unrestricted grammars and Turing machines, many elementary-looking questions inherit the undecidability associated with the halting problem.
Formal languages and meaning
A formal language by itself specifies well-formed expressions but does not determine what those expressions denote. In formal semantics, an interpretation maps syntactic components to objects, functions, or truth conditions within a mathematical structure. Different interpretations may assign different meanings to the same formal expression while leaving its syntactic status unchanged.
In logic, a signature determines the nonlogical symbols from which terms and formulas are constructed. Formation rules define the associated formal language, after which a model supplies semantic values. The separation allows properties such as validity, satisfiability, and derivability to be distinguished precisely.
Programming languages exhibit the same division. A grammar describes the admissible arrangement of tokens, while a static or dynamic semantics specifies the behavior associated with valid programs. Practical language definitions may also impose context-dependent constraints that are inconvenient to express in a context-free grammar, even when the main phrase structure is context-free.
The word “language” therefore refers to several related mathematical objects. It can denote the raw set of accepted strings, a grammar used to generate that set, or a notation equipped with an interpretation. Formal-language theory uses the first meaning as fundamental and treats grammars, automata, and expressions as representations or elements associated with that set.