Shellex.info

在上一篇文章里面，Shellex阐述了将正则表达式转换成NFA的通用方法，算是对以前编译原理课程的回炉重炼了一遍。
下面Shellex将重炼进行下去。对于一个NFA，如何转换成DFA呢？
根据上回说的，一个 NFA 在读入符号串之后，并不确切地知道自动机的下一个状态是什么。但可以肯定的是，下一个状态一定处于某个状态集中。不妨该状态集记做  {q1,q2,…qk}  。
而一个等价的DFA 读入同样的符号串一定处于某个确定的状态上。
这样，都是读入同样的w，  DFA  到达某一个状态，而  NFA  到达某一个状态集。由  w  的任意性，可将  NFA  的所有的状态集和  DFA  的状态一一对应起来。这种对应的前提就是能识别同样的输入串。即  L(M1)=L(M2)  。
所以可以看出，我们要做的就是将 NFA 状态集归并为 DFA 中的状态。
为了归并的成功，Shellex先介绍三种基本操作：
ε-closure(s)：从状态s出发，返回仅仅通过ε边可以到达的最大状态集合
ε-closure(T)：从状态集合T中的每一个状态出发，返回仅仅通过ε边可以到达的最大状态集合
move(T, w)：从状态集合T中的每一状态出发，返回w边指向的下一个状态的集合
接下来Shellex用一个NFA为例，分析整个过程：

可以看到，这是一个典型的NFA。状态1到状态2存在ε边，而状态3有两个b边，分别指向自己和状态4。
S1=ε-closure(1); //S1={1,2}
S1a = move(S1, ‘a’); //S1a = {3}
S1b = move(S1, ‘b’); //S1b = {}
S2 = ε-closure(S1a); //S2 = {3}
S2a = move(S2, ‘a’); //S2a={}
S2b = move(S2, ‘b’); //S2b={3, 4}
S3 = ε-closure(S2b); //S3={3, 4}
S3a = [...]

最近得做一些跟自动机有关的东东，其中一部分可以简要地看作是由一套正则文法生成状态自动机的过程。
什么是正则表达式？
首先我们看看什么是正则表达式。这个东东呢，一般用于描述一个字符串的集合——直接说就是一个正则表达式可能可以匹配一大堆字符串，而这一大堆字符串可以形成一个集合，它们的共同特征就是可以被这个正则表达式匹配。就像去死去死团，但是不同的是去死去死团的团员的共同特征是不被任何异性所匹配——但是这没关系，我们不妨取去死去死团的补集就行了。
反正正则表达是很好啦，因为你只要用一点点在脏话里，就可以骂好多好多人，比如：
Mar(y|k|cus) is son of bitch.
真是非常de省力，唯一的缺点是可能对方不知道你在说什么。
好了，从上面我们可以看出正则表达式中的两个基本结构：

连结 (Concatenation)，比如 bitch，由b, i, t, c, h连接而成
联合 (Union)，比如 y|k|cus，可以认为是y或k或者cus

下面是第三个基本结构，被称为Kleene star (或者 Kleene 闭包)的。因为这个操作是Stephen Cole Kleene发明的。啊啊，其实正则表达式这个东西就是Kleene发明的。这个同学真是非常的牛B，因为他是更加牛B的 阿隆佐 – 丘奇 ( Alonzo Church )——历史上和阿兰 – 图灵 ( Alan Turing ) 并称的人物——的学生。有多牛B呢，这个Kleene还和他的老师，还有图灵，就递归论发表了论文，奠定了可计算理论的根基。啊哈哈哈，真是牛B啊。
嗯，所谓Kleene Star的例子就是这样的。

Kleene Star，比如a*，可以接受空串和若干个a连结组成的串

当然咯，还有一些别的操作，比如我们知道的+，?，集合[]等等，但是这些操作都可以通过上面三个基本操作的组合来完成。
比如+，a+可以认为是aa*
什么是NFA？
要说NFA嘛，我得先说说DFA。所谓DFA，就是Deterministic Finite state Automata的简称。是状态机的一种。通俗的说，就是一大堆状态的集合，里面有一个初始状态和若干终止状态，每个状态可以有若干个输出边前往别的状态。但是要求每个状态的同一种输出边至多只有一个，所以自动机被称为是”Deterministic”的。
比如下面这个例子：
表述的是一个电灯de开关，这个开关每按一下就从’开’状态转换到’关’状态，或者从’关’状态转换到’开’状态。而为了从环保角度出发，在’关’状态才被认为是终止态。

上面的自动机呢，就可以描述这个灯泡的行为模式，或者说可以描述电灯的状态转换过程。输出边就是’开’或者’关’的动作，或者说这个灯泡的开关，只接受这两种动作：“Trun On”，“Trun Off”。而”Trun On”动作只会导致灯的状态变成“On”，“Trun Off”动作只会导致灯的状态变成“Off”，这是确定的，你的外婆都可以预料到的。所以说DFA是确定有限状态自动机。
现在可以说NFA了。这个NFA嘛，全称是Non-deterministic Finite state Automata。也是状态自动机的一种。确切地说，刚才的DFA是NFA的一个子集。和DFA唯一的区别就是他是”Non-deterministic”的，哈，非确定的，每个状态的同一种输出边可以不止一个。
还是用刚才的例子。现在假设我们的电灯有一种新的状态咯～：坏掉了。灯丝被过大的电流烧断了，听上去遭透了，因为一”Trun On”就得准备换灯泡了：

但是我们没法确定的知道哪一次Trun On会导致灯泡坏掉，使得灯泡进入”Down”状态的那次“开”操作看上去跟你昨天开灯的那次操作一模一样（严格的说，每一次点亮灯泡都会导致灯丝的状态发生变化，但是在此简化了）
所以从状态”Off”出来的输出边中，”Trun On”有两条，这就导致没法根据当前状态和输出边确定下一状态，这就是为什么称为非确定性有限自动机的原因。
如何转换？
刚才Shellex说了，正则表达式有三种基本结构。如果能先将这三种基本结构转换成对应的NFA，然后在用这三种基本结构去拼装成完整的NFA是不是很省力呢？
下面就是三种基本正则表达式的NFA
ab:

a*:

a|b:

里面出现了一种叫“None”的边。这个不代表这个边是字面上的“None”，而是指这个边是个空边。也就是说任何“动作”都可以从这个边进入下一个状态。它的学名叫 epsilon 边，一般表示成’ε’，Shellex这里表示成“None”了。
下面我们来考虑正则表达式到NFA转换。给出一个正则串的输入，得到一个NFA的输出。被广泛采用的是Thompson Algorithm，也就是所谓的子集算法。该算法的发明人应该就是写ed编辑器的那个Thompson大牛。该算法的实现和算术表达式的求值非常的类似，需要一个符号栈存放操作符，一个自动机栈存放生成的自动机。算法结束后，可以从自动机栈中Pop一个最终的结果。
比如对于正则表达式(a|b)*cd，求值过程如下：
PUSH a To automaton stack
PUSH [...]

去参加数学建模比赛的时候哈，折腾的要死。Linux下的几个常用的数学分析软件都用了一遍：
Maxima （Mathmatic的开源替代品，Lisp编写，我很赞这个软件）,
Octave（Matlab的GNU替代品，语法最接近Matlab）,
Scilab （又一个Matlab的开源替代品。和Octave的区别是前者使用GNU协议授权，Scilab是法国科学院的开源作品，而且Scilab的文档和资料都要多不少，除了那个该死的tk GUI，还是很好用的。但是从功能上来说，至少在目前我认为，二者差不多）,
Freefem （没有数学基础，这个玩意用不明白，解决偏微分方程(组)的）
Scilab解决常微分方程：
// ———- Simple one dimension ODE (Scilab function external)
// dy/dt=y^2-y sin(t)+cos(t), y(0)=0
function ydot=f(t,y),ydot=y^2-y*sin(t)+cos(t),endfunction
y0=0;t0=0;t=0:0.1:%pi;
y=ode(y0,t0,t,f)
plot(t,y)
C语言接口…
// ———- Simple one dimension ODE (C coded external)
ccode=['#include <math.h>'
'void myode(int *n,double *t,double *y,double *ydot)'
'{'
'  ydot[0]=y[0]*y[0]-y[0]*sin(*t)+cos(*t);’
‘}’]
mputl(ccode,TMPDIR+’/myode.c’) //create the C file
ilib_for_link(‘myode’,’myode.o’,[],’c’,TMPDIR+’/Makefile’,TMPDIR+’/loader.sce’);//compile
exec(TMPDIR+’/loader.sce’) //incremental linking
y0=0;t0=0;t=0:0.1:%pi;
y=ode(y0,t0,t,’myode’);
唔，还有别的常微分solver函数可以使用的。参考scilab的documents的非线性求解(nonlinear)这一章。

Octave是GNU的一个项目，作为最好的Matlab免费替代品之一(另一个是Scilab)，我们可以用它做很多事情…
函数积分：
Octave supports three different algorithms for computing the integral of a function f over the interval from a to b. These are
quad
Numerical integration based on Gaussian quadrature.
quadl
Numerical integration using an adaptive Lobatto rule.
trapz
Numerical integration using the trapezodial method.
Sample:
对函数
f(x) = x * sin (1/x) * sqrt (abs (1 – x))
有
function y = f (x)
y = x [...]