目录

语言概述

单词(token)

语句(sentence)

程序(program)

语言(language)

基本定义

字母表(alphabet)

字母表的乘积

字母表的n次幂

字母表的闭包

句子 

出现(occurrence)

语言概述

单词(token)

按照一定规则由字符(character)组成的串。字符则是由大小写英文字符，各种运算符和分隔符组成的ASCII字符集。

语句(sentence)

或被称为句子。按照一定规则由单词组成的串。

程序(program)

按照一定规则由语句组成的串。

语言(language)

语句的集合。

基本定义

字母表(alphabet)

一个非空集合，字母表中的元素称为该字母表的一个字母(letter)，或者字符(character)。

这个字母表和我们常说的ABCD...Z那个字母表不太一样。"0,1"，“+,-,*,/"甚至是换行符"\n"都可以构成字母表，以下列出几个字母表作为例子。

{a,b,c,d,A,B,C,..,Z}

{0,1}

{+,-,*,/,!,&,=,<,>,\n,\t}

需要注意的是，字母表中的字符应满足整体性和可辨认性（可理解为不可重复性）。

整体性是指假设现在有个字母表中有“\n"，它属于单个字符，是不能被拆分为”\"和"n"的。

而可辨认性也很简单，就是一个字母表内不能出现相同的字母。比如{a,b,a}构成一个句子ab，你没法辨认区分出现的到底是第一个a还是第二个a。

字母表的乘积

直接两两相乘就行

{0,1} {0,1}={00,01,10,11}

需要注意的是字母表乘积不满足乘法交换律，例子如下

{a,b,c} {0,1}={a0,a1,b0,b1,c0,c1}

{0,1} {a,b,c}={0a,0b,0c,1a,1b,1c}

字母表的n次幂

设是一个字母表，它的n次幂递归定义为

其中，是由中的0个字符组成的。这个概念可以类比于集合里的空集。但{}并不是空集，因为实际上也算一个字符串，只不过是一个长度为0的空字符串。  

这个n代表什么呢？假设给个字母表{a,b,c}，那么n=3就是字母表挑2个字符出来，然后两两组合（包括与它本身）的所有集合，即{aa,ab,ac,ba,bb,bc,ca,bc,cc}。也就是{a,b,c}与{a,b,c}相乘，这也符合它的定义。

字母表的闭包

闭包有两种，一种是正闭包，另一种是克林闭包(Kleene closure)。

以下是它们的定义

正闭包

克林闭包

克林闭包的字母表就比正闭包多了个，没了。举个例子就明白了

句子 

又被称为字(word)，行(line)，串(string)，字符行，字符串。

当给定一个字母表以及它的克林闭包时，x若属于它的克林闭包，那么x就被称为字母表上的一个句子。被称为字母表上的一个空句子(null)。比如在下面这个克林闭包中，01就是字母表上的一个句子。

出现(occurrence)

给定一个字母表，对于克林闭包中所有的x，y，当a属于字母表时，句子xay中的a称为a在该句子中的一个出现(occurrence)。（这里出现是作为一个名词来使用的，而不是作为动词使用。）

不难理解，还是上面那个字母表。从克林闭包中取出x,y。再从字母表中取出a。将xay组合在一起构成句子时，如果xay也属于克林闭包，那么有以下三种定义

1.当x=，a的这个出现为字符串xay的首字符，也就是”第一个出现是该字符串的第一个字符“。

2.当y=，a的这个出现为字符串xay的尾字符，也就是”第n个出现是该字符串的最后一个字符“。

3.如果a的某个出现是字符串xay的第n个字符，则y的首字符的这个出现是字符串的第n+1个字符。

定义三这话有点绕。比如x=001,y=110,a=0。xay=0010110。a的第三个出现是xay的第四个字符。y的首字符的出现就是字符串的第五个字符。那如果字母表是这种呢？

一样的，假设取x=0011,y=1100,a=00。xay=0011001100。a的第二个出现是xay的第三个字符“00”，y的首字符“11”仍然是字符串的第五个字符。