关于自动机

自动机理论研究抽象计算装置或“机器”,因为某个叫后缀自动机的东西和编译原理,就来康康这是啥。

一些贯穿自动机理论的概念

字母表

“字母表”是符号的有穷非空集合, 通常使用$\Sigma$表示。

例如:

  1. $\Sigma$ = {0, 1}, 二进制字母表。
  2. $\Sigma$ = {a, b, …, z}, 所有小写字母集合。

“串”(或者单词)是从某个字母表中选择符号的有穷序列。

例如:010101是从$\Sigma$ = {0, 1} 中选出的串。

  • 空串:是出现0次符号的串,记作$\varepsilon$。它是可以从任何字母表中选择的串。
  • 串的长度:定义$\Sigma^k$是长度为$k$的串的集合,标准记号为$|w|$,$|\varepsilon|=0$ 。
  • 字母表的幂:定义$\Sigma^k$为长度为$k$的串的集合,串的每个符号都属于$\Sigma$ 。字母表的所有串的集合约定记为$\Sigma^*$ 。

语言

$\Sigma$是某个具体的字母表,全都从$\Sigma^*$中选出的串的一个集合称为“语言”。如果$\Sigma$是字母表,且$L\subseteq\Sigma^*$,则$L$是$\Sigma$上的语言。

问题

一个“问题”就是判定一个给定的串是否属于某个具体语言的提问。

如果$\Sigma$是字母表,$L$是$\Sigma$上的语言,则问题$L$就是:给定$\Sigma^*$中的一个串$w$,判定$w$是否属于$L$。

因此,任何口头上称为“问题”的东西,都可以表示为语言的成员性。

确定型有穷自动机与非确定型有穷自动机的定义

一个确定型有穷自动机包括:

  1. 一个有穷的状态集合,通常记作$Q$。
  2. 一个有穷的输入符号集合,通常记作$\Sigma$。
  3. 一个有穷的“输入符号”集合
  4. 一个转移函数, 以一个状态和输入符号作为变量,返回一个状态。转移函数通常记作$\delta$。在非形式化代表自动机的途中,用状态之间的箭弧和箭弧上的标记来表示$\delta$。如果$q$是一个状态,$a$是一个输入符号,则$\delta(q,a)$是这样的状态$p$,使得从$p$到$q$有带$a$标记的箭弧。
  5. 一个初始状态,是$Q$中状态之一。
  6. 一个终结状态活接受状态的集合$F$。集合$F$是$Q$的子集。

通常用缩写DFA来指示确定型有穷自动机。通常用五元组记号来讨论DFA: 对于非确定型有穷自动机(NFA),实质上像DFA那样来表示NFA: NFA与DFA唯一的区别在于$\delta$的返回类型。在NFA的情况下,返回值是一个状态集合;在DFA的情况下,返回值是单个状态。

因此,我们可以通过“子集构造”的方法,证明DFA能做NFA所做的一切。