第二章 有限状态机及其扩展

2.1 有限状态机

2.1.1 基本概念

有限状态机是一个五元组

状态转移矩阵：行表示状态机当前所处的状态，列表示将要到达的下一个状态，行列交叉处表示输入字符。

状态转移表

状态转移图

有限字母表：由有限任意符 组成的非空集合，简称字母表，用

字符串：由字符组成的限序列

• 字符串长度：|a|
• 字符串连接：一次把两个字符串串接在一起，用 · 表示，也可以略去不写

语言：给定字母表