DFA的画法

多数程序设计语言单词的语法都能用正规文法(3型文法)描述

正规文法回顾

  文法的任一产生式α→β的形式都为A→aB或A→a，其中A ，B∈VN，a∈ VT 。

  正规文法描述的是VT*上的正规集

---

例如:

  用l表示a~z中的任一英文字母，d表示0~9中任一数字

Ø描述标识符的正规文法为

  <标识符>→l｜l<字母数字>

  <字母数字>→l｜d｜l<字母数字>｜d<字母数字>

Ø描述无符号整数的正规文法

   <无符号整数>→d｜d<无符号整数>

正规式是描述正规集的方便工具

正规式与正规集的递归定义

1.ε和Ф都是∑上的正规式，它所表示的正规集分别为｛ε｝和Ф；

2. 任何ａ∈∑，ａ是∑上的正规式，它所表示的正规集为｛ａ｝；

3.假定ｅ1和ｅ2都是∑上的正规式，他们所表示的正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也都是正规式和他们所表示的正规集；

---

例如：

令S={a，b}， S上的正规式和相应的正规集有

  正规式  正规集

  a  {a}

  a½b    {a,b}

  ab  {ab}

  (a½b)(a½b)  {aa,ab,ba,bb}

  a*  {e ,a,aa,…任意个a串}

  (a½b)*  {e ,a,b,aa,ab ……所有由a和b  组成的串}

正规式和正规文法式等价的，可以相互转换

正规式  →正规文法

1.将∑上的一个正规式r转换成文法G=(VN,VT,S,P)

ØVT= ∑,首先形成产生式S→r,S为G的开始符

Ø不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止

    原产生式

    变换后产生式

  规则1

    A→xy

  A→xB  B→y

  规则2

    A→x*y

  A→xA  A→y

  规则3

    A→x|y

  A→x   A→y

正规文法 →正规式 基本为上述的逆过程

Ø将每条产生式改写为正规式

Ø用代入法解正规式方程组

Ø最后只剩下一个开始符号定义的正规式,其中不含非终结符

正规文法到正规式的转换规则:

    文法产生式

    正规式

  规则1

  A→xB  B→y  A=xy

  规则2

    A→xA|y

    A=x*y

  规则3

  A→x   A→y  A=x|y

有穷自动机(也称有限自动机)

是一种识别装置

作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合

意义:为词法分析程序的自动构造寻找特殊的方法和工具。

分类:

  确定的有穷自动机

  (Deterministic Finite Automata)

  不确定的有穷自动机

  (Nondeterministic Finite Automata)

---

从正规文法到NFA的转换方法

设文法G=(VN,VT,P,S)相应NFA M=(K,∑,f,K0,Z)则

1.∑=VT 

2.K0=S

3.增加一个新的状态T作为终态，Z={T},

4.K=VN∪{T}

5.f由以下方法求得：

  若P中有A→aB，则有f(A,a)=B；

  若P中有A→a， 则有f(A,a)=T；

  若P中有A→ε，则有f(A,ε)=T；