形式语言是一个字母表上的某些有限长字串的集合。一个形式语言可以包含无限多个字串。

语言的形式定义

字母表 Σ 为任意有限集合，ε 表示空串， 记 Σ⁰ 为{ε}，全体长度为 n 的字串为 Σⁿ ， Σ^* 为 Σ⁰∪Σ¹∪…∪Σⁿ∪…， 语言 L 定义为 Σ^* 的任意子集。

注记：Σ^* 的空子集 Φ 与 {ε} 是两个不同的语言。

语言间的运算

语言间的运算就是 Σ^* 幂集上的运算。

• 字串集合的交并补等运算。
• 连接运算：L₁L₂ = { xy | x 属于L₁并且 y 属于L₂ }。
• 幂运算：Lⁿ = L … L （共 n 个 L 连接在一起），L⁰ = {ε}。
• 闭包运算：L^* = L⁰∪L¹∪…∪Lⁿ∪…。
• （右）商运算：L₁/L₂ = {x | 存在 y 属于L₂使得 xy 属于L₁}。

语言的表示方法

一个形式语言可以通过多种方法来限定自身，比如：

• 枚举出各个字串（只适用于有限字串集合）。
• 通过形式文法来产生（参见乔姆斯基谱系）。
• 通过正则表达式来产生。
• 通过某种自动机来识别，比如图灵机、有限状态自动机。

参见

• 计算机科学课程列表

编译原理 | 形式語言

Формален език | Formální jazyk | Formale Sprache | Formal language | Lenguaje formal | Formaali kieli | Langage formel | Linguaggio formale (matematica) | 形式言語 | 형식 언어 | Formele taal | Język formalny | Linguagem formal | Limbaje formale | Формальный язык | Formálny jazyk | Biçimsel dil kuramı