形式语言基本概念（Fundamental Concepts of Formal Languages）

语言 (Language)

定义 (Definition): 在计算机科学中，语言是由有限或无限个字符串（符号序列）组成的集合，这些字符串从某个特定的字母表中选取。

In computer science, a language is a set of strings (sequences of symbols) that are chosen from a specific alphabet, which may be finite or infinite.

集合 (Set)

定义 (Definition): 集合是对象的无序集合，这些对象称为集合的元素。用大写字母表示集合，例如： $A, B, C$ 。

A set is an unordered collection of objects, known as elements of the set. Sets are typically denoted by uppercase letters, such as $A, B, C$ .

示例 (Example):

A = {a, b, c}

字母表 (Alphabet)

定义 (Definition): 字母表是一个有限的符号集合，用符号 $Σ$ 表示。字母表中的每个符号称为字母。

An alphabet is a finite set of symbols, typically denoted by the symbol $Σ$ . Each symbol in the alphabet is called a letter.

示例 (Example):

Σ = {0, 1}

形式语言 (Formal Language)

定义 (Definition): 形式语言是从某个字母表 $Σ$ 中选取的一些字符串的集合。形式语言用来描述语法结构和计算模型。

A formal language is a set of strings of symbols that are chosen from an alphabet $Σ$ . Formal languages are used to describe syntactic structures and computational models.

示例 (Example): 如果 $Σ = {a, b}$ ，则 $Σ^{*}$ 表示由 $Σ$ 生成的所有可能字符串的集合，包括空串 $ϵ$ 。例如： ${ϵ, a, b, aa, ab, ba, bb, aaa, \dots}$

If $Σ = {a, b}$ , then $Σ^{*}$ denotes the set of all possible strings generated by $Σ$ , including the empty string $ϵ$ . For example: ${ϵ, a, b, aa, ab, ba, bb, aaa, \dots}$

基本标识方法 (Basic Notation Methods)

联接 (Concatenation)

两个字符串 $u$ 和 $v$ 的联接表示为 $uv$ ，是将 $u$ 和 $v$ 中的符号依次连接形成的新字符串。

The concatenation of two strings $u$ and $v$ , denoted by $uv$ , is a new string formed by appending the symbols of $v$ to the symbols of $u$ in order.

示例 (Example): 若 $u = ab$ 且 $v = c d$ ，则 $uv = ab c d$ 。

If $u = ab$ and $v = c d$ , then $uv = ab c d$ .

Kleene 星 (Kleene Star)

对于字母表 $Σ$ ， $Σ^{*}$ 表示 $Σ$ 上所有可能字符串（包括空串 $ϵ$ ）的集合。

For an alphabet $Σ$ , $Σ^{*}$ denotes the set of all possible strings over $Σ$ , including the empty string $ϵ$ .

长度 (Length)

字符串 $w$ 的长度表示为 $∣ w ∣$ ，表示 $w$ 中符号的个数。

The length of a string $w$ , denoted by $∣ w ∣$ , represents the number of symbols in $w$ .

示例 (Example): 若 $w = ab c$ ，则 $∣ w ∣ = 3$ 。

If $w = ab c$ , then $∣ w ∣ = 3$ .

子串 (Substring)

字符串 $v$ 是字符串 $w$ 的子串，若存在字符串 $u_{1}$ 和 $u_{2}$ 使得 $w = u_{1} v u_{2}$ 。

A string $v$ is a substring of a string $w$ if there exist strings $u_{1}$ and $u_{2}$ such that $w = u_{1} v u_{2}$ .

逆序 (Reversal)

字符串 $w$ 的逆序表示为 $w^{R}$ ，是将 $w$ 中的符号按逆序排列的新字符串。

The reversal of a string $w$ , denoted by $w^{R}$ , is a new string formed by reversing the order of the symbols in $w$ .

示例 (Example): 若 $w = ab c$ ，则 $w^{R} = c ba$ 。

If $w = ab c$ , then $w^{R} = c ba$ .

重要概念 (Important Concepts)

空语言 (Empty Language)

空语言表示为 $\emptyset$ ，它是一个不包含任何字符串的集合。

The empty language, denoted by $\emptyset$ , is a set that contains no strings.

空串 (Empty String)

空串表示为 $ϵ$ ，它是长度为零的字符串。

The empty string, denoted by $ϵ$ , is a string of length zero.

幂集 (Power Set)

集合 $S$ 的幂集表示为 $P (S)$ ，它是由 $S$ 的所有子集组成的集合。

The power set of a set $S$ , denoted by $P (S)$ , is the set of all subsets of $S$ .

示例 (Example): 若 $S = {a, b}$ ，则 $P (S) = {\emptyset, {a}, {b}, {a, b}}$ 。

If $S = {a, b}$ , then $P (S) = {\emptyset, {a}, {b}, {a, b}}$ .

语言运算 (Operations on Languages)

并 (Union)

两个语言 $L_{1}$ 和 $L_{2}$ 的并表示为 $L_{1} \cup L_{2}$ ，它是所有属于 $L_{1}$ 或 $L_{2}$ 的字符串的集合。

The union of two languages $L_{1}$ and $L_{2}$ , denoted by $L_{1} \cup L_{2}$ , is the set of all strings that belong to $L_{1}$ or $L_{2}$ .

交 (Intersection)

两个语言 $L_{1}$ 和 $L_{2}$ 的交表示为 $L_{1} \cap L_{2}$ ，它是所有属于 $L_{1}$ 和 $L_{2}$ 的字符串的集合。

The intersection of two languages $L_{1}$ and $L_{2}$ , denoted by $L_{1} \cap L_{2}$ , is the set of all strings that belong to both $L_{1}$ and $L_{2}$ .

差 (Difference)

两个语言 $L_{1}$ 和 $L_{2}$ 的差表示为 $L_{1} - L_{2}$ ，它是属于 $L_{1}$ 但不属于 $L_{2}$ 的字符串的集合。

The difference of two languages $L_{1}$ and $L_{2}$ , denoted by $L_{1} - L_{2}$ , is the set of all strings that belong to $L_{1}$ but not to $L_{2}$ .

连接 (Concatenation)

两个语言 $L_{1}$ 和 $L_{2}$ 的连接表示为 $L_{1} L_{2}$ ，它是所有形如 $uv$ 的字符串的集合，其中 $u \in L_{1}$ 且 $v \in L_{2}$ 。

The concatenation of two languages $L_{1}$ and $L_{2}$ , denoted by $L_{1} L_{2}$ , is the set of all strings of the form $uv$ where $u \in L_{1}$ and $v \in L_{2}$ .

Kleene 闭包 (Kleene Closure)

语言 $L$ 的 Kleene 闭包表示为 $L^{*}$ ，它是所有 $L$ 的字符串的零个或多个连接构成的集合。

The Kleene closure of a language $L$ , denoted by $L^{*}$ , is the set of all strings formed by zero or more concatenations of strings from $L$ .

示例 (Example): 若 $L = {a}$ ，则 $L^{*} = {ϵ, a, aa, aaa, \dots}$ 。

If $L = {a}$ , then $L^{*} = {ϵ, a, aa, aaa, \dots}$

前缀 (Prefix)

定义 (Definition): 字符串 $u$ 是字符串 $w$ 的前缀，若存在字符串 $v$ 使得 $w = uv$ 。

A string $u$ is a prefix of a string $w$ if there exists a string $v$ such that $w = uv$ .

示例 (Example): 若 $w = ab c$ ，则 $u = a$ 和 $u = ab$ 都是 $w$ 的前缀。

If $w = ab c$ , then $u = a$ and $u = ab$ are prefixes of $w$ .

后缀 (Suffix)

定义 (Definition): 字符串 $v$ 是字符串 $w$ 的后缀，若存在字符串 $u$ 使得 $w = uv$ 。

A string $v$ is a suffix of a string $w$ if there exists a string $u$ such that $w = uv$ .

示例 (Example): 若 $w = ab c$ ，则 $v = c$ 和 $v = b c$ 都是 $w$ 的后缀。

If $w = ab c$ , then $v = c$ and $v = b c$ are suffixes of $w$ .

子序列 (Subsequence)

定义 (Definition): 字符串 $v$ 是字符串 $w$ 的子序列，若可以通过从 $w$ 中删除一些字符（可以是零个）得到 $v$ ，但不改变剩余字符的顺序。

A string $v$ is a subsequence of a string $w$ if $v$ can be obtained by deleting some (possibly zero) characters from $w$ without changing the order of the remaining characters.

示例 (Example): 若 $w = ab c$ ，则 $v = a c$ 是 $w$ 的子序列。

If $w = ab c$ , then $v = a c$ is a subsequence of $w$ .

形式语言的属性 (Properties of Formal Languages)

封闭性 (Closure Properties)

形式语言在某些运算下是封闭的，即运算的结果仍然是形式语言。这些运算包括并、交、差、连接和 Kleene 闭包。

Formal languages are closed under certain operations, meaning the result of these operations is still a formal language. These operations include union, intersection, difference, concatenation, and Kleene closure.

封闭性运算 (Closure Operations):

并 (Union): 如果 $L_{1}$ 和 $L_{2}$ 是形式语言，则 $L_{1} \cup L_{2}$ 也是形式语言。

If $L_{1}$ and $L_{2}$ are formal languages, then $L_{1} \cup L_{2}$ is also a formal language.
交 (Intersection): 如果 $L_{1}$ 和 $L_{2}$ 是形式语言，则 $L_{1} \cap L_{2}$ 也是形式语言。

If $L_{1}$ and $L_{2}$ are formal languages, then $L_{1} \cap L_{2}$ is also a formal language.
差 (Difference): 如果 $L_{1}$ 和 $L_{2}$ 是形式语言，则 $L_{1} - L_{2}$ 也是形式语言。

If $L_{1}$ and $L_{2}$ are formal languages, then $L_{1} - L_{2}$ is also a formal language.
连接 (Concatenation): 如果 $L_{1}$ 和 $L_{2}$ 是形式语言，则 $L_{1} L_{2}$ 也是形式语言。

If $L_{1}$ and $L_{2}$ are formal languages, then $L_{1} L_{2}$ is also a formal language.
Kleene 闭包 (Kleene Closure): 如果 $L$ 是形式语言，则 $L^{*}$ 也是形式语言。

If $L$ is a formal language, then $L^{*}$ is also a formal language.

逆 (Reversal)

定义 (Definition): 语言 $L$ 的逆表示为 $L^{R}$ ，它包含 $L$ 中所有字符串的逆序字符串。

The reversal of a language $L$ , denoted by $L^{R}$ , consists of the reversals of all strings in $L$ .

示例 (Example): 若 $L = {ab, c d}$ ，则 $L^{R} = {ba, d c}$ 。

If $L = {ab, c d}$ , then $L^{R} = {ba, d c}$ .

形式语法 (Formal Grammar)

定义 (Definition): 形式语法是描述语言结构的一种方法，由一个四元组 $G = (N, Σ, P, S)$ 组成，其中：

A formal grammar is a method for describing the structure of languages, consisting of a four-tuple $G = (N, Σ, P, S)$ , where:

$N$ 是一组非终结符号 (a set of non-terminal symbols)
$Σ$ 是一组终结符号 (a set of terminal symbols)
$P$ 是一组产生式规则 (a set of production rules)
$S$ 是开始符号 (the start symbol)

例子 (Example)

假设有一个形式语法 $G = ({S}, {a, b}, {S \to a S b ∣ ϵ}, S)$ 。这个语法生成的语言是 ${ϵ, ab, aabb, aaabbb, \dots}$ 。

Consider a formal grammar $G = ({S}, {a, b}, {S \to a S b ∣ ϵ}, S)$ . The language generated by this grammar is ${ϵ, ab, aabb, aaabbb, \dots}$ .

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer