自然语言处理（一）：文法与形式语言的基本概念

一、基本概念

设 Σ 为字符的一个有限集合；其中每个元素被称为字符；由 Σ 中符号连接而成的有限序列被称为 Σ 上的字符串。

教材对此进行了明确阐述。简单来说，在这种情况下被称为字符串，并由多个字符组成。特别地，在这种情况下被称为空串，并表示为 ε。

既包含空串又基于字符串 Σ 构建的所有字符串的集合称为 Σ*。例如当 Σ=abcd 时 Σ* 包括由a b c d中的字符构成的所有可能排列组合以及空串 ε。

2.字符串相接：举个例子说吧，在Python中变量赋值如x = 'abc'、y = 'def'。将这两个变量相接表示为xy = 'abcdef'。而当我们将一个变量重复相接时，则称其为该变量的一次自连。类似地，在处理多个相同变量相接时，则直接将其数量作为指数使用。

3.字符串集合 的乘积：设A, B是符号串的集合，则A, B的乘积定义为：AB = {xy | x ∈ A, y ∈ B}。

例如 设A={aa, bb}, B={cc, dd, ee}，则 AB={aacc, aadd, aaee, bbcc, bbdd, bbee}

4. stringset of closure: suppose V is a stringset over the character set Σ, then its closure is defi