woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

正则文法与正则语言

一、右线性文法


定义:(右线性文法)一个文法 G=(V, T, P, S) 如果只包含如下模式的产生式

A-> xB

A-> x

其中 A, B in V, x in T*,则称 G 是右线性的。右线性文法产生的语言称为右线性语言。

二、右线性语言与正则语言的等价性


定理:给定一个右线性文法 G,则存在一个 nfa A,使得 L(G)=L(A).

可以把 nfa A 具体地构造出来。比如 V_i-> xV_j,则添加两个状态 V_i, V_j, 并在 V_i, V_j 间添加若干``匿名''状态(名字可以随机选取,只要不冲突)使得从状态 V_i 通过 x 能到达 V_j, 而通过 x 的任何前缀就会死掉。另给定一个状态 V_f 作为唯一的终止状态,对产生式 V_k -> x, 在状态 V_k V_f 间添加若干``匿名''状态,使得通过 x 可以从状态 V_k 到达 V_f.

定理:给定一个正则语言 R, 则存在一个右线性文法 G,使得 L(G)=R.

R 对应的 dfa A, 转移函数为 f. S_i, S_j A 的两个状态,并且 f(S_i, a) = S_j。这个状态转移可以用 S_i->aS_j 来刻画。若 S_k 为接受状态,则可以用 S_k->e 来刻画。

三、正则文法与正则语言

从上面的两个定理可以知道,右线性文法与 dfa 是等价的。类似地,我们有左线性文法,它与 dfa 也是等价的。所以左、右线性文法是等价的。


定义:(正则文法)左线性文法等价于右线性文法,它们统称为正则文法。

定理:正则文法与 dfa 等价。

posted on 2009-10-31 14:59 肥仔 阅读(1590) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理