经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 计算机原理 » 查看文章
正规文法与正规式
来源:cnblogs  作者:Raicho  时间:2019/10/16 13:21:43  对本文有异议

 3型文法也叫作正规文法,它对应于有限状态自动机,它是在2型文法的基础上满足:A->a|aB(右线性)或A->a|Ba(左线性)。如果有A->a,A->aB,B->a,B->cB则符合3型文法的要求。但是A->ab,A->aB,B->a,B->cB或A->a,A->Ba,B->a,B->cB则不符合3型文法的要求。也就是说,不能够推导出两个终结符,而且左线性和右线性只能使用一种,不能够同时出现。

1.分别写出描述以下语言的正规文法和正规式:

(1)L1={abna|n≥0}。

(2)L2={ambn|n≥1,m ≥1}

(3)L3={(ab)n|n≥1}

 答:(1) S -> aA

        A -> bA | a

   (2)S -> aABb

       A -> aA | ε

      B -> bB | ε

   (3)S -> abβ

       β -> ab | ε

2.将以下正规文法转换到正规式

 ·Z→0A
 ·  A→0A|0B
 ·  B→1A|ε

 答:Z = 0A

  A = 0A + 0B

  B = 1A + ε

  A = 0A + 0(1A + ε) = 0A + 01A + 0 

  A = aA | b

  Z = 0(0 | 01)*0

 

Z→U0|V1
  U→Z1|1
  V→Z0|0

答:Z = U0 + V1

  U = Z1 + 1

  V = Z0 + 0 

  Z = (Z1+1)0 + V1

  Z = (Z1+1)0 +(Z0+0)1

  Z = Z10 + 10 +Z01 + 01

  Z = Z(10+01)+10+01

  Z = (10+01)*1001

 

S→aA
  A→bA|aB|b
  B→aA

答:S = aA

  A = bA + aB + b

  B = aA

  A = bA + a(aA) +b  = (b + aa)A +b

  S = (b | aa)*b

 

I→l|Il|Id

答: I = I + Il + Id

   I = l + I(l +d)

   I = (l +d)*l

 

原文链接:http://www.cnblogs.com/lzhdonald/p/11684484.html

 友情链接:直通硅谷  直通硅谷 怎么样 mac软件下载