计算机是一个很复杂的模型，首先从一个简单点模型入手。
2.1有穷自动机（FA）
有穷自动机是关于存储量极其有限的计算机很好的模型。
2.1.1 有穷自动机的形式定义
可以用状态图非形式的描述有穷自动机，也可以用形式语言描述。用形式语言来定义有穷自动机优点：
- 首先形式定义是精确的，他能消除在有穷状态自动机中任何不明确的疑点。
- 其次形式定义提供了一种表示方法，好的表示方法有助于思考和表达你的思想。
以下摘自百度百科
数学、逻辑和计算机科学中，形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。
如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。
按一定规律构成的句子或符号串的有限或无限的集合。
定义 2.1 有穷自动机是一个5元组，其中：
1）是一个有穷集合，叫做状态集。
2）是一个有穷集合，叫做字母表。
3），是状态转移函数。
4）是起始状态。
5）是接受状态集。
2.1.2 有穷自动机举例
设A是机器M接受的全部字符串集，称A是机器M的语言，记作L（M）=A。又称M识别A或M接受A
-
-
f
-
$A={\omega|\omega 含001最为字符串}
这个地方可以展开描述下字符串查找子串的方法，KMP貌似不是最优的。
2.1.3 计算的形式定义
如果一个语言能被有穷自动机识别，则称它是正则语言。
2.1.5 正则运算
并、连接、星号
正则语言类在并运算下封闭
正则语言类在连接运算下封闭
2.2 非确定性
在非确定型机器中，在任何一点，下一个状态可能存在若干选择。
2.2.1 非确定型有穷自动机的形式定义
** 定义2.17** 非确定型有穷自动机是一个5元组。
2.2.2 NFA与DFA的等价性
显然，DFA是一台NFA
每一台非确定型有穷自动机都有一台等价的确定型有穷自动机。
一个语言是正则的，当且仅当一非确定型有穷自动机识别它。
2.3 正则表达式
可以用正则运算符构造描述语言的表达式。
2.3.1正则表达式的形式定义
2.3.2 与有穷自动机的等价性
一个语言是正则的，当且仅当可以用正则表达式描述它。
2.4 非正则语言
有穷自动机的局限性。
非正则语言：
网友评论