chapter3-有限状态自动机

  • 有限状态机 FSA
  • 确定性的识别器 DFSA
  • 确定性的识别器 NFSA:深度优先搜索 or 广度优先搜索
  • 形式语言

有限状态自动机 finite-state automation, FSA

前面一章节中的正则表达式只是一种用于文本搜索的方便的元语言,它是描述有限状态机的一种方法。

任何正则表达式又可以用有限状态机来实现(除了使用存储特性的那些正则表达式)。比如上一章中用于描述羊的语言的正则表达式: /baa+!/ 就可以表示为这样的有限自动机:

FSA可以用来识别(或接受)符号串。接受方式如下:把输入想象成一个长长的带子(tape),带子上的一个单元格(cell)可以写一个符号:

怎么理解这个输入带子和自动机呢?就是当输入带上的字母和自动机中离开当前状态的弧相匹配时,就穿过这个弧,进入到自动机中的下一个状态和带子上的下一个符号。比如上图中初始状态 \(q_0\) 只有遇到b时才会匹配成功而进入下一个状态和输入符号,所以上图中的自动机不能接受输入。对图2.10中 \(q_3\) 状态,他可以匹配 a或!.

我们可以用状态转移表(state-transition table)来表示自动机。状态转移表可以表示初始状态、接收状态和符号在状态之间的转移情况。

一个有限自动机可以用下面5个参数来定义:

其中Q表示N种状态的集合,\(\Sigma\) 表示有限的输入符号字母表, \(q_0\)是初始状态, \(F\in Q\) 是终极状态。 \(\delta(q,i)\) 是转移矩阵,其中 \(q\in Q,i\in \Sigma\). \(\delta(q,i)\) 返回一个新的状态,\(q'\in Q\),则 \(\delta(q,i)\) 是从 \(Q \times \Sigma\) 到 \(Q\) 的一个关系.

在HMM中,状态转移矩阵是N*N的,跟这里有区别。

DFSA

可以用状态转移表来识别字符串,就是把一个字符串输入进去,然后用自动机来判别是accept还是reject。这种算法是“确定性的是识别器”,deterministic算法,简称 D-RECOGNIZE.

伪代码:

在图2.13中,状态之间的转移矩阵是 transition-table[current-state, tape[index]]. current-state表示行,tape[index]表示列。其中index = index + 1.

如果将状态转移矩阵中的空状态称为失败状态(fail state)或者吸收状态(sink state).那么对任何状态和任何输入,自动机都能找到可以转移的地方。

NFSA

存在某个状态,难以判断接下来怎么走的自动机称为非确定的FSA(或NFSA).如下图:

还有一种NFSA,用到了 \(\epsilon-\) 转移的新弧。如果到达了状态3,那么可以进入带有标记!的弧,也可以不看带子上的符号,直接转移到状态2.

那么其对应的状态转移表如下图:

用NFSA来接受符号串: 有三种方法:

  • 回退
  • 前瞻
  • 并行

这里我们采用回退法:

代码阅读:

function ND-RECOGNIZE(tape, machine) return accept or reject

  1. 创建进程表(agenda): 其中的元素是current-search-state, 是由自动机的一个结点(状态)和带子上的一个位置组合而成的。 agenda = {(Initial state of machine, beginning of tape)} current-search-state = NEXT(agenda)

  2. 主回路:用来确定输入带子上的全部内容是否都被自动机全部识别了,这可以用ACCEPT-STATE?函数实现,如果当前搜索状态既包括一个接受的机器状态,也包含一个子结尾的指针,那么就返回accept.这一步类似于 D-RECOGNIZE. 如果不行,那就调用 GENERATE-NEW-STATE 来生成一系列可能的下一个状态。

    1
    2
    3
    4
    5
    6
    7
    8
    if ACCEPT-STATE?(current-search-state) return ture :
    return ACCEPT
    else
    agenda = agenda and GENERATE-NEW-STATE(current-search-state) //这一步不太理解???
    if agenda is empty:
    return reject
    else
    current-search-state = NEXT(agenda)

NEXT函数从进程表返回一个为探测过的状态。那么怎么定义函数NEXT,这是一个值得研究的问题。

  • 进程表用stack实现,那就是深度优先搜索(depth-first search)或后进先出(Last In First Out, LIFO).
  • 进程表用queue实现,那就是广度优先搜索(breadth-first search)或先进先出(First In First Out, FIFO).
  1. ACCEPT-STATE? 函数用来确定输入带子上的全部内容是否都被自动机成功的识别了。

    1
    2
    3
    4
    5
    6
    7
    function ACCEPT-STATE? (search-state)  returns ture of false
    current-node = the node search-state is in
    index = the point on the tape search-state is looking at
    if index is at the end of the tape and current-node is an accept state of machine:
    return ture
    else
    return false

  2. GENERATE-NEW-STATE函数用与选取一种为访问过的路径 需要理解的是:在NEXT(agenda)中,agenda采用的是stack或queue, 那么意味着在只有一种选择的结点处,走过就删掉了,只有有两种选择的地方,另外一种会储存在agenda中。所以current-search-state = NEXT(agenda)生成的是有两种选择处的未访问过的路径。那么GENERATE-NEW-STATE函数就是生成这样的一个路径,然后在ACCEPT-STATE?中判断。

识别就是搜索: 把符号串输入当做输入带,然后用自动机来识别。其实也可以看作是搜索的过程。

深度优先搜索:

广度优先搜索:

形式语言

形式语言是早期处理自然语言处理技术中,当时几乎是唯一的方法,可以用于描述自然语言的语法规律,能最大限度的逼近自然语言,并且很容易生成语言内容。 形式语言和自动机之间存在的对应关系,使其天生就容易被计算机处理。

虽然现在自然语言处理主要是基于统计模型来处理的,但形式语言仍然会出现在很多论文中。

图论

  • 无向图 G = (V, E), V 表示定点, E表示无向边。

  • 有向图 G = (V, E), V 是定点,E 是有向边

  • 连通图和回路

文法,形式语法

在用计算机系统,来判断一个句子是否是某语言的合法句子时,从句子和语言的结构特征上着手是非常重要的。一般可以通过这个句子是否能有给定语言对应的文法产生来作出判断,如果能,他就是合法的,否则,他就是非法的。对一类语言,可以在字母表上按照一定的规则,根据语言的结构特点,定义一个文法。用文法作为相应语言的有穷描述不仅可以描述出语言的结构特性,而且还可以产生出这个语言的所有句子。