- 一般我们会用状态图来描述一个有限自动机(Finite Automata)。它有且只有一个起始状态(在状态图中,一个从不知道什么地方来的箭头指向的状态),有一些接受状态(状态图中有两个圈圈起来的状态)。
- 有限自动机的输出是接受或者拒绝。
- 下图是一个有限自动机 (我们叫它
),它能接受所有以1结尾的串。

- 有限自动机的形式定义
- 有限自动机是一个5元组(元组的定义在文末)
,其中
是一个有限的集合,叫做状态集。
是一个有限的集合,叫做字母表。
(这个记号的定义在文末)是一个转移函数。
是起始状态。
是接受状态集。
- 有限自动机是一个5元组(元组的定义在文末)
- 一个机器
接受的全部字符串的集合
,叫做机器
的语言(语言的定义在文末),记作
。
- 现在我们可以给出在有限自动机上的计算的定义了。
- 设
是一台有限自动机,
是一个字符串且每个
都是字母表
中的一个字符。如果有一个
中的状态序列
满足以下3个条件:
- 则
接受
。(想问怎么去掉这句话前面的圆点并且保持缩进)
- 设
- 一个语言如果能被某种有限自动机接受,那么它就被称为正则语言。
- 正则运算:
- 并:
- 连结:
- 星号:
- 并:
- 正则语言类在三种正则运算下封闭,即两种正则语言(对于星号运算来说,只需要一种)做正则运算,得到的结果仍是正则语言。
附:各种定义
- 元组:有限的序列。5元组即包含5个元素的元组。
:即笛卡尔积,是第一个元素属于
,第二个元素属于
的所有有序对组成的集合。
,
称为函数或者映射,是一个输入-输出的关系。
- 语言:一些字符串的集合。
博主太厉害了!真是浅显易懂的讲解!受教了!
多少钱一条?我也要干这行