陈斌彬的技术博客

Stay foolish,stay hungry

编译原理-正规式和有限自动机

正规式:

正规式:正则表达式,表示正规集的工具。

一个正规式对应一个正规文法(3型文法)

之间能够进行准换

三个基本规则:

A->xB,B->y  则 A=xy。
A->xA|y  则A=x*y  (x*代表x从0到无穷多个)
A->x,A->y 则A=x|y

正规式主要用到了递归的思想,无论遇到多复杂的正规式都可以拆分成上面这三种形式,然后进行解题。

有限自动机(有穷自动机):

DFA(Deterministic Finite Automation ):确定的有限自动机

表达式:M=(S,∑,f,So,Z)
1. S为一个有限状态集合
2. ∑是一个字母表,它所包含的的每个元素称为一个输入字符;
3. f是一个从SX∑(笛卡尔乘积)至S的单值部分映射。f(S,a)=s'意味着当现在的状态为s,输入字符a时,将转换到下一状态s'.s'为s的一个后继状态。
4. So∈S,是唯一的初态;
5. Z⊆S,是一个终态集。

NFA(Nondeterministic Finite Automata):不确定的有限自动机

如果理解了有限自动机,则无限自动机和它的区别就是上面的第四项。

So⊆S,它的初态不是唯一的,而是一个集合。

NFA向DFA的转换:

这个转换是一个比较简单的过程。

  1. 如果有一个不确定的有限自动机,则可以转化为图的方式。此处不详述怎样转图的方式。
  2. 先将初态确定,然后根据输入的每个元素可以得到哪些状态,依次列表。
  3. 这些状态集合可以称为这个有限状态集合n个子集。按0,1,2……的顺序编号。
  4. 因为这些子集之间的关系是输入一个确定值确定的,所以这些子集之间存在一些关系,即把这些子集的关系写出来完成NFA向DFA的转换。

正规式与有限自动机之间的转换:

img