目录
字符串运算
在计算机科学领域形式语言理论中，经常用到各种字符串函数；但是符号不同于计算机编程中所用到的，某些在理论领域中常用的函数，在编程中很少用到。本文定义其中一些基本术语。.
上下文有关语言
在理论计算机科学中，上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基层级中的四类文法之一。当然它在理论和实践中都是最少使用的。.
上下文无关文法
上下文无关文法（context-free grammar，縮寫為CFG），在计算机科学中，若一个形式文法 G.
串接
在形式語言理論（特別是編程語言），字串串接（Concatenation），又稱字串相加、連接、串連、相連，指將兩個字串的首尾相接的操作。例如「foo」和「bar」串接後便成了「foobar」。部分語言，串接的操作是透過將串接運算子放在兩個字串（運算元）之間。.
查看 上下文无关语言和串接
下推自动机
在自动机理论中，下推自动机（Pushdown automaton）是使用了包含数据的栈的有限自动机。.
并集
在集合论和数学的其他分支中，一组集合的并集（台湾叫做聯--集、港澳叫做--、大陆叫做--）是这些集合的所有元素构成的集合，而不包含其他元素。.
查看 上下文无关语言和并集
交集
数学上，两个集合A和B的交集是含有所有既属于A又属于B的元素，而没有其他元素的集合。.
查看 上下文无关语言和交集
形式语言
在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
查看 上下文无关语言和形式语言
克莱尼星号
Kleene 星号，或稱Kleene 闭包，德语稱 Kleensche Hülle，在數學上是一種適用於字符串或符號及字元的集合的一元運算。當 Kleene 星号被應用在一個集合V時，寫法是V^*。它被廣泛用於正则表达式。.
CYK算法
CYK算法（Cocke–Younger–Kasami algorithm，縮寫為CYK algorithm）是由約翰·科克，Younger和共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串~w \in \Sigma^* 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（~O(n^3) ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。 对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。.
编程语言
编程语言（programming language），是用来定义计算机程序的形式語言。它是一种被标准化的交流技巧，用来向计算机发出指令。一种计算机语言让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下所应当采取的行动。 最早的编程语言是在電腦發明之前產生的，當時是用來控制及自動演奏鋼琴的動作。在電腦領域已發明了上千不同的编程語言，而且每年仍有新的编程語言誕生。很多编程語言需要用指令方式說明計算的程序，而有些编程語言則屬於宣告式編程，說明需要的結果，而不說明如何計算。 编程语言的描述一般可以分為及語義。語法是說明編程語言中，哪些符號或文字的組合方式是正確的，語義則是對於編程的解釋。有些語言是用規格文件定義，例如C語言的規格文件也是ISO標準中一部份，2011年後的版本為ISO/IEC 9899:2011，而其他55語言（像Perl）有一份主要的文件，視為是。.
查看 上下文无关语言和编程语言
补集
在集合论和数学的其他分支中，存在--的两种定义：--和--。.
查看 上下文无关语言和补集
闭包 (数学)
数学中，若对某个集合的成员进行一種运算，生成的仍然是这个集合的成员，则该集合被称为在這个运算下闭合。 例如，实数在减法下闭合，但自然数不行：自然数 3 和 7 的减法 3 − 7 的结果不是自然数。 类似的，一个集合被称为在某些运算的搜集下闭合，如果它在每个运算之下都闭合。 一个集合在某个运算或某些运算的搜集下闭合被称为满足闭包性质。闭包性质经常作为公理，通常叫做闭包公理。现代集合论通常这样定义：运算为在集合间的映射。所以向一个结构增加闭包性質作为公理是多余的，尽管它对于子集是否闭合的问题仍有意义。 当一个集合 S 在某个运算下不闭合的时候，我们通常可以找到包含 S 的最小的闭合集合。这个最小闭合集合被称为 S 的（关于这个运算的）闭包。例如，若把自然数集看作实数集的子集，它在减法下的闭包就是整数集。一个重要的例子是拓扑闭包。闭包的概念推广为伽罗瓦连接，进一步为。 注意集合 S 必须是闭合集合的子集，這樣才能定义闭包算子。在前面的例子中，实数在减法下闭合是重要的，减法不总是在自然数的定义域中有定义的。 闭包这个词的两种用法不应混淆。前者用来提及闭合的性质，而后者提及包含不闭合集合的最小闭合集合。简要的说，一个集合的闭包满足闭包性质。.
正则语言
正规语言又称正则语言是满足下述相互等价的一组条件的一类形式语言：.
查看 上下文无关语言和正则语言
正则文法
在计算机科学中，正规文法是产生式规则取下述形式的一种形式文法（N, Σ, P, S）：.
查看 上下文无关语言和正则文法
泵引理
在可计算性理论中的形式语言理论中，泵引理声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。 泵引理是1961年由 Y.
查看 上下文无关语言和泵引理