加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

正则表达式 – 常规语言的定义

发布时间:2020-12-13 21:54:15 所属栏目:百科 来源:网络整理
导读:我已经尝试过,烧掉了我的大脑来理解 Discrete Mathematics and its Applications(Rosen)中常规语言的定义,而没有达到理解为什么定义与本书中的定义相同的目标.在页面(789),我正在改写定义: 类型3语法定义为: w1 -- w2 其中w1是非终端,w2的形式如下: w2 =
我已经尝试过,烧掉了我的大脑来理解 Discrete Mathematics and its Applications(Rosen)中常规语言的定义,而没有达到理解为什么定义与本书中的定义相同的目标.在页面(789),我正在改写定义:

类型3语法定义为:

w1 --> w2

其中w1是非终端,w2的形式如下:

w2 = aB
w2 = a

其中B是非终端,a是终端.一个特例是当w1是起始符号而w2是lambda(空字符串)时:

w1 = S
S --> lambda

我无法找到两个问题的答案.首先,为什么w2不能成为Ba的形式.第二,为什么lambda仅允许用于起始符号.该书指出,常规语言相当于有限状态自动机,我们可以很容易地看到我们可以为这两种情况构建FSA.我查看了其他资源,这些资源中不存在这些限制.

First,Why can’t w2 be of the form Ba.

以W作为起始符号采用以下语法:

W -> lambda
W -> aX
X -> Wb

它生成{an bn:n natural},这不是常规语言.因此,如果您只想生成常规语言,则此限制至关重要.或者,您可以允许w2 = Ba,但禁止使用类型规则w2 = aB – 这也提供常规语言.该语法将构建一个“向后”的单词.

如果您允许这两种类型的规则,您将获得一个名为linear languages的类.

Second,Why lambda is only allowed for the starting symbol only.

这不是必要的限制.

您可以消除lambda对非终结符号的所有使用:采取一些规则W – > lambda,删除它,并替换所有规则U – > aW与U – >; aW和U – >一个.显然你不能消除使用lambda作为终端符号(语言不再产生空字).

因此,在许多地方使用lambda的每个类型3语法都可以“标准化”为仅使用lambda作为起始符号的语法.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读