计算理论 字母表：一个有穷的符号集合。字母表上的字符串是该字母表中的符号的有穷序列。一个字符串的长度是它作为序列的长度。连接 反转 Kleene星号 L* ，连接L中0个或多个字符串得到的所有字符串的集合。有穷自动机：描述能力和资源极其有限的计算机模型。有穷自动机是一个5元组M=(K,s,F),其中1）K是一个有穷的集合，称为状态集2）是一个有穷的集合，称为字母表3）是从KXK的函数，称为转移函数4）sK是初始状态5）FK是接收状态集M接收的语言是M接收的所有字符串的集合，记作L(M).对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机有穷自动机接受的语言在并、连接、Kleene星号、补、交运算下是封闭的。每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。一个语言是正则的当且仅当它被有穷自动机接受。正则表达式：称R是一个正则表达式，如果R是1）a，这里a是字母表中的一个元素。2），只包含一个字符串空串的语言3），不包含任何字符串的语言4)(R1R2),这里R1和R2是正则
