内容发布更新时间 : 2024/12/25 4:33:56星期一 下面是文章的全部内容请认真阅读。

(1) 给出语言{anbncm|n≥1,m≥0}的上下文无关文法。 S->AC A->ab | aAb C->epsilon|cC

构造步骤如下~

1）你看a跟b出现次数相同，那多半它们在一个式子里，c次数跟它们不一样，多半在另一式子里，那么ab相关的非终结符就取名A，c相关的就取名C；

2）先看c，要出现c的m次方，那很简单就是C->cC，然后知道m可以是0，那么很简单再带上一个epsilon就是了；

3）然后看aaaabbbb...这个式子，明显重复的是ab，所以ab是最底层用来重复的道具所以有A->ab，然后再怎么生成呢=-= 两边套a跟b，所以就是A->aAb，最后看一眼，哦ab不能出现0次啊，那就不用加epsilon=-=； 4）最后把它们合起来S->AC就行了。

(2) 写出一个文法，使其语言是偶正整数集合。 要求：（1）允许0开头，（2）不允许0开头 I．可以以 0 开头

答：题意应该是可以以任意个 0 开头，即允许 0023,0004 这样的数字，那么结 果应该是：

(0-9)*((2|4|6|8)|((1|2|3|...|8|9)0+))

S->H(D|C) A->1|2|3|...|8|9 B->0|1|2|3|...|8|9 H->BH|epsilon Z->0 C->AZ|CZ D->2|4|6|8

H 表示(0-9)* C 表示((1|2|3|...|8|9)0+) 思路：首先想到必须有一个(0-9)*这样的来构成所有的数字，然后正偶数必须 以 02468 结尾，但是以 0 结尾可能带来 000,00,0 这

样的结果，明显不符合题 意，所以，以 0 结尾的数字必须串长不小于 2，所以把末尾的(0|2|4|6|8)换成 了(2|4|6|8)|((1|2|3|...|8|9)0+)。

II．不许以 0 开头

答：(((1-9)(0-9)*(0|2|4|6|8))|(2|4|6|8))

改造成文法： S->HC|D A->1|2|3|...|8|9 B->0|1|2|3|...|8|9 H->A|HB C->0|2|4|6|8 D->2|4|6|8

H 表示(1-9)(0-9)* 思路：正数表示没有 0，没有空串，偶数表示以 02468 结尾，但是以 0 结尾不 能串长为 1，不许以 0 开头表示必须以 1-9 开头。

所以得到：(1-9)表示不以 0 开头，(0-9)*可以构成所有的数字串，结尾一定是 24680 所以有

(1-9)(0-9)*(0|2|4|6|8)，但是观察发现我表达出来的串至少两位，于是在补 上串长为一的串(2|4|6|8)，得到我的结果：(((1-9)(09)*(0|2|4|6|8))|(2|4|6|8))