# Formal language
A **formal language** is a set of strings, each of finite length, built from a finite alphabet of symbols; the set may be infinite, and membership in it is determined purely by the form of the strings, not by any meaning they carry[1](https://www.vssut.ac.in/lecture_notes/lecture1423726104.pdf). Formal language theory studies the mathematical and computational properties of such sets, chiefly through the grammars that generate them and the automata that recognize them[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC3367686/).
| Key fact | Detail |
|---|---|
| Definition | A (possibly infinite) set of finite-length strings over an alphabet; the definition involves only syntax, no more nor less[1](https://www.vssut.ac.in/lecture_notes/lecture1423726104.pdf) |
| Standard description | Alphabet, formation rules, and intended translations; only the third part assigns meaning[3](https://notes.amittai.studio/logic/sentential-logic/formal-languages-and-well-formed-formulas) |
| Specifying device | Usually a formal grammar, such as a regular grammar or context-free grammar, also called its formation rule[1](https://www.vssut.ac.in/lecture_notes/lecture1423726104.pdf) |
| Founding paper | Noam Chomsky, "Three Models for the Description of Language," IEEE Transactions on Information Theory 2(3): 113–124, September 1956[4](https://cir.nii.ac.jp/crid/1363388844526316672) |
| Hierarchy | Regular, context-free, context-sensitive, and unrestricted languages, matched to finite automata, pushdown automata, and Turing machines[5](https://somr.info/lib/Chomsky_1959.pdf) |
| Practical use | Compilers use regular languages to convert character strings to tokens and context-free languages to parse token sequences into programs[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf) |
| Parsing cost | Deciding whether a string belongs to a context-free language takes time growing with the third power of the string length[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC3367686/) |
## Definition and basic objects
The basic objects are the alphabet, the string, and the language itself. An alphabet is a finite set of symbols; a string is a finite sequence of symbols from it; and a language is any set of such strings. The definition is deliberately spare: while formal language theory usually concerns languages described by syntactical rules, the concept itself is only a set of finite-length strings[1](https://www.vssut.ac.in/lecture_notes/lecture1423726104.pdf). Because the words are considered without any meanings, such a set is called a formal language[7](https://gyires.inf.unideb.hu/KMITT/a51/ch01.html).
In mathematical logic the same idea appears with a three-part description: the alphabet of symbols, the formation rules that pick out the grammatically correct strings (the well-formed formulas), and the intended translations into ordinary language. Only the third part assigns meaning; the first two are pure syntax, and someone knowing only the alphabet and formation rules could manipulate the language while remaining ignorant of what it means[3](https://notes.amittai.studio/logic/sentential-logic/formal-languages-and-well-formed-formulas).
## Grammars and generation
A formal language is often defined by means of a formal grammar, such as a regular grammar or a context-free grammar, also called its formation rule[1](https://www.vssut.ac.in/lecture_notes/lecture1423726104.pdf). A grammar is defined as a quadruple of nonterminal symbols, terminal symbols, production rules, and a start symbol[8](https://archive.nptel.ac.in/content/storage2/courses/106103070/modules/module-1/lecture-2/topic-1/s6.htm). Generation proceeds by rewriting: starting from the start symbol, rules of the form \( A \to w \) replace a nonterminal inside a string until only terminals remain, and the language of the grammar is the set of terminal strings reachable this way[9](https://www.andrew.cmu.edu/user/ko/pdfs/lecture-7.pdf).
A grammar can be read as a recursive recipe. For the language \( L = \{ a^{n} b^{n} : n \geq 0 \} \), the two rules \( S \to \varepsilon \) and \( S \to aSb \) generate the empty string and then wrap any existing string with an \( a \) on the left and a \( b \) on the right, so that \( S \to aSb \to aaSbb \to aaabbb \) derives \( aaabbb \)[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf).
## The Chomsky hierarchy
The classification of grammars into types comes from [Noam Chomsky](https://www.edgepedia.org/noam-chomsky), a linguist at the [Massachusetts Institute of Technology](https://www.edgepedia.org/massachusetts-institute-of-technology) whose 1956 paper "Three Models for the Description of Language" examined finite-state processes, phrase-structure grammars, and transformational grammars as models of English[4](https://cir.nii.ac.jp/crid/1363388844526316672). His 1959 paper "On Certain Formal Properties of Grammars" studied a sequence of restrictions on rewriting systems, limiting them first to Turing machines and finally to finite automata, with intermediate systems that assign a phrase-structure description to each generated sentence; each restriction narrows the set of languages that can be generated[5](https://somr.info/lib/Chomsky_1959.pdf).
The resulting levels are standard in the literature. A language is regular, context-free, context-sensitive, or unrestricted if and only if some grammar of the corresponding type generates it[10](https://web.stanford.edu/~kiparsky/Papers/panini-1.pdf). Each level pairs with a recognizer: regular languages with finite automata, context-free languages with pushdown automata, and the higher levels with increasingly powerful Turing-machine models[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf).
**What the levels separate.** Regular languages are efficient to recognize but limited in power; they cannot represent the overall structure of a C program, nor the language of properly nested parentheses, which can be proved non-regular by intersecting it with a regular language and mapping the result to \( \{ 0^{n} 1^{n} \} \)[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf). Context-free grammars capture such nested structure, which is why [parse trees](https://www.edgepedia.org/parse-tree) for sentences and programs are central to both linguistics and compiling[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf).
## Closure and decision properties
The classes differ sharply in how they behave under set operations. Context-free languages are closed under union, concatenation, and [Kleene star](https://www.edgepedia.org/kleene-star), but not under intersection or complement: the languages \( \{ a^{n} b^{n} c^{*} \} \) and \( \{ a^{*} b^{n} c^{n} \} \) are each context-free, yet their intersection is \( \{ a^{n} b^{n} c^{n} \} \), which is not[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf). These closure facts have been verified mechanically: a Coq proof-assistant formalization covers closure under union, concatenation, and Kleene star, grammar simplification, and the existence of Chomsky Normal Form for context-free grammars[11](https://arxiv.org/abs/1510.09092).
Decision problems also vary by level. Membership for context-free languages is decidable in cubic time, meaning the time needed to decide whether a string \( x \) belongs to \( L(\mathcal{G}) \) grows with the third power of the length of \( x \)[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC3367686/). For context-sensitive grammars, membership is decidable in principle, but computing the answer may be algorithmically so complex that it is, for practical purposes, intractable[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC3367686/).
## Applications
The hierarchy maps directly onto language-processing software. A compiler or a natural-language understanding program uses regular languages to convert character strings into tokens such as words, variable names, and function names, and then uses context-free languages to parse token sequences into functions, programs, or sentences[6](https://mfleck.cs.illinois.edu/cs373-notes.pdf). Regular expressions, a declarative notation for regular languages, are likewise used in text tools such as those in Unix[12](https://ics.uci.edu/~goodrich/teach/cs162/notes/).
Across logic and computer science at large, formal languages serve as the basis for well-formed formulas, which consist of a finite string of symbols drawn from a specified alphabet and put together according to the grammar a formal language establishes.
## Refinements and current research
The four-level hierarchy is not the last word. Two refinements are relevant to research in cognitive science: the mildly context-sensitive languages, located between the context-free and context-sensitive levels, and the sub-regular hierarchy, which distinguishes several levels of complexity within the class of regular languages[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC3367686/).
The field remains active across a broad front. DLT 2024, the 28th International Conference on Developments in Language Theory, held in [Göttingen](https://www.edgepedia.org/gottingen), gathered research spanning grammars, acceptors, and transducers that operate on words, trees, and graphs; links between formal languages and artificial neural networks; algebraic approaches to automata theory; decidability problems; and connections with cryptography, concurrency, complexity theory, and logic.[13](https://link.springer.com/book/10.1007/978-3-031-66159-4)
## References
1. [Automata Theory lecture notes, Veer Surendra Sai University of Technology](https://www.vssut.ac.in/lecture_notes/lecture1423726104.pdf)
2. [Formal language theory: refining the Chomsky hierarchy, PMC](https://pmc.ncbi.nlm.nih.gov/articles/PMC3367686/)
3. [Formal Languages and Well-Formed Formulas, Amittai study notes](https://notes.amittai.studio/logic/sentential-logic/formal-languages-and-well-formed-formulas)
4. [Three models for the description of language, CiNii Research record](https://cir.nii.ac.jp/crid/1363388844526316672)
5. [Noam Chomsky (1959). On Certain Formal Properties of Grammars, Information and Control 9](https://somr.info/lib/Chomsky_1959.pdf)
6. [Lecture notes, CS 373: Theory of Computation, University of Illinois](https://mfleck.cs.illinois.edu/cs373-notes.pdf)
7. [Chapter 1. Automata and Formal Languages, University of Debrecen](https://gyires.inf.unideb.hu/KMITT/a51/ch01.html)
8. [NPTEL IIT Guwahati, Automata and Grammars](https://archive.nptel.ac.in/content/storage2/courses/106103070/modules/module-1/lecture-2/topic-1/s6.htm)
9. [Formal Languages, Automata and Computation: Context Free Languages, Carnegie Mellon University](https://www.andrew.cmu.edu/user/ko/pdfs/lecture-7.pdf)
10. [Background: Formal Language Complexity, Stanford University](https://web.stanford.edu/~kiparsky/Papers/panini-1.pdf)
11. [Formalization of context-free language theory, arXiv](https://arxiv.org/abs/1510.09092)
12. [Course Notes, CS 162 Formal Languages and Automata Theory, UC Irvine](https://ics.uci.edu/~goodrich/teach/cs162/notes/)
13. [Developments in Language Theory, DLT 2024 Proceedings, Springer](https://link.springer.com/book/10.1007/978-3-031-66159-4)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Logical calculi and logical syntax › Proof theory › Structural proof theory*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license