[资工]离散 文法/语言

楼主: qoojordon (颖川琦)   2014-11-10 22:11:55
几个离散的 文法 问题
来自小黄离散五版 13-37 与13-41
Q1: 下册13-35 设计grammer生成 L={w|w属于{a,b}* , w中a的个数是3的倍数 }
内容中有段叙述 ,
  S表示含3k个a的字串 
  A表示含3k+1个a的字串
其中一个文法推论为 A→aS .....(后略)
没有考虑 A→Sa , 虽然Sa这型的也属于aS的其中一员 , 还是觉怪怪的...
另外 , 书上设计文法的题目 , 大多推论的右侧如果同时有 N 与 T的成员 ,
都会统一先写T再写N , 是刚好题目有交换的性质? 还是type3 与 type2 的文法
生成的语言都符合这个现象?
Q2-1: 下册13-37文法分类
type1 , type2的文法分别称为 context-sensitvie 和 context-free
context是指? 是说生成的语言和什么相关吗 ? 看书上的例子大多都为
type2与type3, 目前都是定义操作 , 土法炼钢写出生成的L , 条件比较严苛
的文法(如type3 或 type2)其生成的L是否有通用的型式呢?
Q2-2: 13-41范例3
(3) S→aAB , AB→c , A→b , B→AB
(3)是type 0 文法 , 原因是红色的推论吗 ? 天外飞来一个c?

Links booklink

Contact Us: admin [ a t ] ucptt.com