内容发布更新时间 : 2024/5/21 21:57:05星期一 下面是文章的全部内容请认真阅读。

25． 下列语言或文法确切属于按乔姆斯基（Chomsky）分类的哪种类型,请填在（ ）内。 （1） L1={ a0n1nbdm | n>0，m >0} ( ) （2） L2={ anbncnbm | n≥0,m>0 } ( ) （3） L3={ anbmc| n≥0,m>0 } ( ) （4） G[A]:A→aB|ε B→Ab|a ( ) （5） G[E]:E→E+E|E*E|(E)|i ( ) 答：

（1） L1={ a0n1nbdm | n>0，m >0} ( 2 型 ) （2） L2={ anbncnbm | n≥0,m>0 } ( 1型 ) （3） L3={ anbmc| n≥0,m>0 } ( 3型 ) （4） G[A]:A→aB|ε B→Ab|a ( 2型 ) （5） G[E]:E→E+E|E*E|(E)|i ( 2型 )

26． 按指定类型给出下列语言的文法。

(1) L1={ candbm| n≥0,m>0 } 用正规文法。

(2) L2={ 0na1nbmcm| n>0，m ≥0} 用二型文法。 答：

（1）解：描述L1语言的正规文法如下： S→cA A→aA|B B→dD D→bD|ε

（2）解：描述L2语言的二型文法如下： S→AB

A→0A1|0a1 B→bBc|ε

27． 写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列 答：

⑴.(+,a,b) ⑵.(-,a,b) ⑶.(/,⑴,⑵) ⑷.(*,b,c) ⑸.(+,a,⑷) ⑹.(-,⑶,⑸)

28． 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 答：

逆波兰表示：

abc*＋ab＋/d－

三元式序列：

① (*，b，c) ② (＋，a，①) ③ (＋，a，b) ④ (/，②，③) ⑤ (－，④，d)

29． 将下面的条件语句表示成四元式序列：

if a>b then x:=a+b*c else x:=b-a; 答：

(1) ( j>, a, b, (3)) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x)

(6) ( j, , , (9)) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( … … )

30． 翻译成四元式序列。

While a＞0 ∨b＜0 do Begin

X：＝X＋1；

if a＞0 then a：＝a－1 else b：＝b＋1 End； 答：

(1) (j＞，a，0，5) (2) (j，－，－，3) (5) (＋，×，1，T1) (6) (：＝，T1，－，×) (7) (j≥，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1， T3) (13) (：＝，T3，－，b) (14) (j，－，－，1) (15)

31． 已知文法G(S) ： S→a|∧|(T) T→T，S|S

写出句子((a，a)，a)的规范归约过程及每一步的句柄。 答：

句型 归约规则 句柄

((a，a)，a) S→a a ((S，a)，a) T→S S ((T，a)，a) S→a a ((T，S)，a) T→T，S T，S ((S)，a) T→S S ((T)，a) S→S(T) (T) (S，a) T→S S (T，a) S→a a (T，S) T→T，S T，S (T) S→(T) (T) S