编译原理(RE正则表达式和有限状态自动机)

RE正则表达式与有限状态自动机的等价

正则表达式:

• RE<=>ε-NFA或者NFA之间的转换 :

  证明: a 一个字符,怎么去表示一个有限状态自动机?

  • 首先:针对于这个a,一定表示的是a作为一个边条件,然后从一个初始状态转换到另外的一个终止状态
  • 第二个可能,这个a是一个ε,那和上述依然一致
  • 第三个可能:a是一个空集,这里起到的作用是链接中转的可能.

递归-UNION:

E1+E2==>ε-NFA,假设这里有一个ε-NFA,E1+E2表示的是E1并上E2的值,从而将跳转到一个终止状态

但是E1对应了一个转换方式,E2也对应了一个转换方式,该怎么转换呢?

具体操作:

一个初始状态q0,然后利用ε转换到E1再去跳转,或者利用ε转换到E2

再去走到终止状态,但这个时候有两个终止状态了,所以最末尾还有一个真正的终止状态

有点类似于进行了一个或的运算

E1@E2=>ε-NFA,假设E1@E2,字符串的拼接需要去如何构建一个NFA呢?

具体操作:

两个NFA==>由于这里是字符串的拼接,所以在一个NFA状态转换之后,可以无条件转换为另一个新的NFA

这样去处理E1@E2即可

E*=>ε-NFA,这里的话,作为闭包{a,aa,aaaaa,…..}最终到终止状态,从正则表达式到ε的转换

任意给定一个正则表达式,完成其语言L1的判定程序,字符集是{0,1},运算包括E={0,1}|E+E|E@E|E*

010*1=>正则表达式定义,这个东西同时也是上下文无关文法(用于刻画表达式的)

上下文无关文法:

可以实现递归:0的n次方和1的n次方和(01)的n次方

上下文无关文法,主要用于定义