语言

定义

  形式语言中的形式意为语言的所有规则都是被明确指定的,不考虑隐喻和深层含义等等因素,同时也意味我们更重视语言的外在形式,而非它的含义。通俗一点来说,也就是说仅仅关注一段字符串是否符合某语言的语法,其中出现的单词是否是正确的,而不关注这段字符串具体表达的语义正不正常,比如"I like eating Tuesday"这种看着非常滑稽的字符串也是合法的,因为他遵循了英语的语法,单词也都是正确的,仅仅是他的语义比较奇怪而已,我们把可能出现在语言中的所有最基本的单元所构成的有限集叫做字母表(alphabet),用\Sigma表示,而一个包含由字母表中的字母所构成的字符串的集合被称为语言(language),这个集合中的字符串(也就是允许在语言中出现的字符串)被称为单词(words)。字母表里的不一定非要是拉丁字母,对于字符串来说,唯一的要求是出现在字符串中的字母个数必须是有限的。我们也允许没有任何字母的字符串存在,这种字符串叫做空字符串(empty string/null string),用希腊字母\varLambda表示,无论字母表和语言是什么样子的,空字符串永远都是\varLambda,也就是说所有语言的空字符串都是\varLambda,如果空字符串是语言中一个合法的单词,那么这个单词也是\varLambda如果组成两个单词的字母以及它们的顺序是一致的,就认为这两个单词是相同的。为了避免混淆,我们一般不把符号\varLambda(这里仅仅说的是这个符号)作为字母表的一员。
  有关不包含任何字母的单词、\varLambda、和不包含任何单词的语言之间有着细微但是又非常重要的差别,我们用空集的符号\phi来表示一个没有任何单词的语言,注意,此时\varLambda并非语言\phi的一个单词,因为语言\phi是没有单词的。对于一个不包含\varLambda的语言\mathcal{L},如果我们想要他包含\varLambda,那么可以使用集合的并运算,也就是\mathcal{L}+\lbrace \varLambda\rbrace,这个语言和\mathcal{L}是不相同的,因为他加入了一个新的单词\varLambda,然而,如果是\mathcal{L}+\phi,就和原语言L相同了,因为没有新单词被添加进来。注意,尽管不包含任何单词,但是\phi本身也是一种语言。另外,我们并不要求字母表中的所有字母都要在语言中出现(比如eth这个单词在现代英语里就不存在)。
  定义一个语言可以用两种方法:(1). 给出字母表并且列出所有单词 (2). 给出字母表并给定一套选择有效单词的规则,注意,对于第二种方法而言,这套规则是有效的当且仅当它可以在有限的时间内决定一个由字母表中的字母构成的字符串是否是一个合法的单词。这套规则也可以以两种形式存在,(1). 这套规则可以告诉我们如何去测试一个字符串是否是一个合法的单词;(2). 这套规则可以用一套清晰的过程告诉我们如何构造语言中的所有单词。

EXAMPLE
考虑一个语言,他的字母表只有x一个字母:
\Sigma=\lbrace x \rbrace
我们可以通过"任何非空字符串都是一个单词"来定义该语言:
L_1=\lbrace x,xx,xxx,xxxx,...\rbrace
可以换一种写法:
L_1=\lbrace x^n\ for\ n=1,2,3,...\rbrace
注意: 在这个例子中,\varLambda并不在语言\mathcal{L}_1里,可以这么做,但没必要(雾)

拼接

  语言的拼接(concatenation)操作,也就是两个字符串放在一起形成新的字符串,比如在上述的语言\mathcal{L}_1中,可以拼接xxxxx得到xxxxx,我们可以用如下的方式定义这种拼接:
x^n与x^m拼接得到x^{m+n}
也可以用字母a指代xxx,字母b指代xx,那么:
ab=xxxxx

注意,并非在所有语言中,拼接的结果都是另一个单词,比如,对于语言:

\begin{aligned}
\mathcal{L}_2&=\lbrace x,xxx,xxxxx,xxxxxxx,...\rbrace \\
&=\lbrace x^{odd}\rbrace \\
&=\lbrace x^{2n+1}\ for\ n=0,1,2,3,...\rbrace
\end{aligned}

a=xxxb=xxxxx都在语言\mathcal{L}_2中,但是他们的拼接ab=xxxxxxxx就不在\mathcal{L}_2中了,注意\mathcal{L}_2\mathcal{L}_1的字母表相同,同样,在这个例子中,把拼接的顺序交换得到的单词是相同的:
ab=xxxxxxxx=ba
但是并非对于所有语言的任意两个单词都是这样,比如在英语中,"house"和"boat"拼接得到"houseboat",但是反过来的"boathouse"就和"houseboat"不同,这里的不同并非因为他们的含义不同,而是说他们不是同一个单词(上文提到过,字母与排列顺序都相同的才是相同的单词)

反转

DEFINITION:
令函数length表示字符串中字母的个数,例如,如果在语言\mathcal{L}_1中,a=xxxx,则:
length(a)=4
对于任何包含\varLambda的语言,有:
length(\varLambda)=0

我们也可以用两种方式定义包含\varLambda的语言:

\begin{aligned}
\mathcal{L}_4&=\lbrace \varLambda,x,xx,xxx,xxxx,...\rbrace \\
&=\lbrace x^n\ for\ n=0,1,2,3,...\rbrace
\end{aligned}

注意x^0等同于\varLambda而非代数中的x^0=1,因为在这里x^0的意思是把字母x重复0次

DEFINITION
定义函数reverse,如果a是语言\mathcal{L}中的一个单词,则reverse(a)得到一个将a中的字符反向排列所组成的字符串,称作a的反转,即便这个反转后的字符串并非是\mathcal{L}中的单词
EXAMPLE

\begin{aligned}
reverse(xxx)&=xxx \\
reverse(xxxxx)&=xxxxx \\
reverse(145)&=541
\end{aligned}

注意,对于字母表为\varSigma=\lbrace 1,2,3,4,5,...\rbrace的语言\mathcal{G}来说,reverse(140)=041,而041并不是\mathcal{G}的一个单词

Kleene闭包

DEFINITION
给定字母表\varSigma,我们希望有一种方法,能够定义一种由\varSigma中的字母所组成的任意字符串所组成的语言(包括\varLambda),这种语言称作这个字母表\varSigma闭包(closure),写作在字母表符号后接上一个星号角标:
\varSigma^\ast
这种标记也被称作Kleene star,而Kleene是该学科的奠基人之一
EXAMPLE
对于\varSigma=\lbrace x\rbrace,有
\varSigma^\ast=\lbrace \varLambda,x,xx,xxx,xxxx,xxxxx,...\rbrace
对于\varSigma=\lbrace 0,1\rbrace,有
\varSigma^\ast=\lbrace \varLambda,0,1,00,01,10,11,000,001,010,...\rbrace
对于\varSigma=\lbrace a,b,c\rbrace,有
\varSigma^\ast=\lbrace \varLambda,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,...\rbrace

我们可以吧Kleene star当做一种由字母表中的字母所组成的字符串所构成的长度无限的语言,所谓长度无限指的是该语言拥有无限多个单词,而每个单词的长度是有限的,注意,当我们去罗列一个语言的时候,应当像上文中的例子一样按照字典序(lexicographic order)排列

DEFINITION
\mathcal{S}是单词的集合,则\mathcal{S}^\ast代表所有的可以由拼接\mathcal{S}的元素所构成的有限长度的字符串,包括\varLambda在内(注意此处的方法是拼接)
EXAMPLE

\begin{aligned}
令\mathcal{S}&=\lbrace aa,b\rbrace,有\\
\mathcal{S}^\ast&=\lbrace \varLambda与任何由aa和b组成的单词\rbrace \\
&=\lbrace \varLambda与任何a与b组成的字符串,其中a出现的次数为偶数\rbrace \\
&=\lbrace \varLambda,aa,b,aab,baa,bbb,aaaa,aabb,baab,bbaa,...\rbrace
\end{aligned}

为了能够证明某个单词是在\mathcal{S}^\ast里面的,我们需要将其分解为\mathcal{S}中的单词,比如aabbaab可以分解成(aa)(b)(b)(aa)(b),其中被分解后的每个子串都是\mathcal{S}中的单词,注意,aabbaab只有这么一种划分方法,这种情况下我们说对aabbaab的划分是唯一的(unique),另外一些情况下则不是唯一的,比如对于\mathcal{S}^\ast=\lbrace x^n\ for\ n=0,1,2,3,...\rbracex^6就即可以被划分为x^2x^2x^2也可以被划分为x^3x^3

注意,对于\varSigma=\phi(\phi\ refers\ to\ the\ empty\ set)(注:这里的\phi意味着该语言的字母表中没有任何字母),有\varSigma^\ast=\lbrace \varLambda\rbrace,这和对于\mathcal{S}=\lbrace \varLambda\rbrace(注:这里代表着该语言唯一合法的单词是\varLambda),有\mathcal{S}^\ast=\lbrace \varLambda\rbrace是不同的,虽然他们的结果看上去一致,但是后者是因为两个\varLambda拼接在一起还是\varLambda(因为\varLambda是空串),而前者是因为空的字母表只能构成空的字符串。

Kleene闭包总是会产生一个无限的语言,除非构成它的集合是以上两种情况中的一种

此外还有一种情况,当想要让Kleene闭包包含至少一个属于集合的字符串的拼接的时候,可以使用记号\scriptstyle +而非\scriptstyle \ast

EXAMPLE
对于\varSigma=\lbrace x\rbrace,有
\varSigma^+=\lbrace x,xx,xxx,...\rbrace

换言之,对于:

\begin{aligned}
\mathcal{S}=\lbrace strings\ without\ \varLambda\rbrace,&有\mathcal{S}^+=\mathcal{S}^\ast-\lbrace \varLambda\rbrace \\
\mathcal{T}=\lbrace letters\rbrace,&有\mathcal{T}^+=\mathcal{T}^\ast-\lbrace \varLambda\rbrace \\
\mathcal{S}\ is\ language\ with\ word\ \varLambda,&有\mathcal{S}^+=\mathcal{S}^\ast
\end{aligned}

注意以上蕴含的一点,仅当\varLambda \in\mathcal{S}\mathcal{S}^+才会和\mathcal{S}^\ast相等,因为只有此时\varLambda才符合"包含至少一个属于集合的字符串"

无限集合上的Kleene闭包

  对于单词集合\mathcal{S},我们可以用\mathcal{S}^\ast获得它的闭包,我们可以再尝试对\mathcal{S}^\ast取闭包,记作:(\mathcal{S}^\ast)^\ast\ 或\ \mathcal{S}^{\ast\ast}

如果\mathcal{S}并非空集或者仅包含\varLambda,则\mathcal{S}^\ast是无限的,注意到前面要求语言可能出现的所有字符串中的字母个数都应当是有限的,也即每个单词的长度也是有限的,因此第二次取闭包的操作是合法的,因为闭包的定义提到闭包中的字符串个数是无限的,但是每个字符串的长度是有限的,而在此基础上再取一次闭包得到的结果中的字符串长度依然是有限的。

定理1:
对于任意字符串集合\mathcal{S}\mathcal{S}^\ast=\mathcal{S}^{\ast\ast}
Remark:
\mathcal{S}=\lbrace a,b\rbrace,则\mathcal{S}^\ast是由所有可以被ab所构成的有限长字符串的集合,假设我们对\mathcal{S}^\ast再次取闭包,则对于其中的元素aababaaaaaba,拼接起来之后可以得到aababaaaaaba,这个字符串是属于\mathcal{S}^{\ast\ast}的,但是要注意到他同样仅仅由ab构成,而这能够说明他又是属于\mathcal{S}^\ast的,这就像是人类是由分子构成的,而分子是由原子构成的,所以人类也是由原子构成的,能够由人类体内的分子组合而成的东西,也同样可以由人类体内的原子组合而成
证明:
引理1:
\mathcal{S}^{\ast\ast}\sube\mathcal{S}^\ast
Proof:
由于\mathcal{S}^{\ast\ast}是由\mathcal{S}^\ast中出现的字符串拼接而成,而\mathcal{S}^\ast又由\mathcal{S}中的字符串拼接而成,根据拼接的定义,\mathcal{S}^{\ast\ast}中的所有字符串都由\mathcal{S}中的字符串拼接而成,因此有\mathcal{S}^{\ast\ast}\sube\mathcal{S}^\ast
引理2:
对于任意\mathcal{A}\mathcal{A}\sube\mathcal{A}^\ast
证明:
因为\mathcal{A}^\ast即为所有由\mathcal{A}中的零个,一个或多个字符串所拼接而成的新字符串所组成的集合,因此\mathcal{A}^\ast也包含所有由\mathcal{A}中的一个字符串所单独组成的字符串,所以有
\forall_{a\in\mathcal{A}}(a\in\mathcal{A}^\ast)\implies\mathcal{A}\sube\mathcal{A}^\ast

\mathcal{S}^\ast=A,则\mathcal{S}^{\ast\ast}=A^\ast
\therefore \mathcal{S}^\ast\sube\mathcal{S}^{\ast\ast}(由Lemma 2.)
\therefore \mathcal{S}^\ast=\mathcal{S}^{\ast\ast}(由Lemma 1.)

构造性证明

  假设我们需要对\mathcal{S}=\lbrace \varLambda,xx,xxx\rbrace证明\mathcal{S}^\ast包含所有的x^n,其中n\neq 1,首先,我们假设存在一些字符串使得这些字符串无法由xxxxx\varLambda构造而成。
  很明显,如果该假设成立,则存在一个最小的数字m使得x^m无法由xxxxx构造而来,既然如此,说明\forall_{n \lt m}(x^n可以由xx和xxx构造而来),那么我们想要构造x^m就只需要拼接x^{m-2}xx即可,以此类推,我们就可以很轻松的把上述过程变成一个形式化的证明,来论证\mathcal{S}^\ast包含了所有x^n,其中n\neq 1
  类似这样,通过给出构造手段来确定某物存在的证明手段叫做构造性证明(proof by constructive algorithm)

证明技巧

回文串

  考虑语言\mathcal{P}=\lbrace any\ string\ x\ such\ that\ reverse(x)=x\rbrace,给定任意字符串s,证明或证否s\in\mathcal{P}
  证明方法:直接证明reverse(x)=x,或令k=length(s)s中的一第一个元素是s_1,第二个是s_2,一直到s_k,尝试证明\mathop{\forall}\limits_{i=1}^{\lfloor k/2\rfloor}(s_i=s_{k-i+1})

EXAMPLE:
\mathcal{P}是在\varSigma=\lbrace a,b\rbrace上面的语言(包括\varLambda),证明\forall_{x\in\mathcal{P}}(\forall_{n\in\mathbb{N}}(x^n\in\mathcal{P}))
证明1:
对于任意n\in\mathbb{N}
n=0时,x^0=\varLambda
n\neq 0时,令k=length(x),展开x^n有:

x^n=(x_1x_2x_3...x_k)(x_1x_2x_3...x_k)\underbrace{...}_{\text{n-3 times}}(x_1x_2x_3...x_k)

因为reverse(x)=x,有x_1=x_k,x_2=x_{k-1}...
对于reverse(x^n)来说,x^n会沿着一个轴反转,轴所在的位置是x的中心,而轴所处的x沿着轴左右是完全对称的,轴的左侧和右侧分别还有\frac {n-1} 2x,注意到\frac {n-1} 2是一个整数,即左侧的每个x在右侧都有与之对应的另一个x,其中左侧xx_1对应右侧的x_kx_2对应x_{k-1}...因此左侧的\frac {n-1} 2x和右侧的\frac {n-1} 2x也是对称的,因此x^n沿着轴也是完全对称的,这蕴含了reverse(x^n)=x^n,即x^n\in\mathcal{P}
证明2:

x^n=(x_1x_2x_3...x_k)(x_1x_2x_3...x_k)\underbrace{...}_{\text{n-3 times}}(x_1x_2x_3...x_k)

因为x\in\mathcal{P},所以(x_1x_2x_3...x_k)=(x_kx_{k-1}x_{k-2}...x_1),即

\begin{aligned}
x^n&=(x_1x_2x_3...x_k)(x_1x_2x_3...x_k)\underbrace{...}_{\text{n-3 times}}(x_1x_2x_3...x_k) \\
&=(x_kx_{k-1}x_{k-2}...x_1)(x_kx_{k-1}x_{k-2}...x_1)\underbrace{...}_{\text{n-2 times}}(x_kx_{k-1}x_{k-2}...x_1) \\
&=reverse(x^n)
\end{aligned}

EXAMPLE:
证明\mathcal{P}中长度为2n的单词与长度为2n-1的单词数量一致
证明:
因为\forall_{x\in\mathcal{P}}(reverse(x)=x),所以相对于单词反转的轴而言,轴左侧和轴右侧可能的所有排列组合方式数量是相同的,因此对于:
1. 长度为2n的单词,它的所有排列组合方式有2^\frac {2n} 2
2. 长度为2n-1的单词,它的对称轴本身是一个字母,左侧有n-1个字母,右侧也有n-1个字母,因此一共有2^{n-1}中可能,加上中间作为对称轴的字母本身有两种可能,因此一共有2^{n-1}*2=2^n
因此,长度为2n的单词和长度为2n-1的单词数量一致


乱我心者,今日之日多烦忧