题目
令文法G6为 N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G6 的语言L(G6)是什么?(2) 给出句子0127、34和568的最左推导和最右推导。
令文法G6为 N→D|ND
D→0|1|2|3|4|5|6|7|8|9
(1) G6 的语言L(G6)是什么?
(2) 给出句子0127、34和568的最左推导和最右推导。
题目解答
答案
解:(1)L(G6)={a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9}}
(2)N =>ND=> NDD=> NDDD=> DDDD=> 0DDD=> 01DD=> 012D=> 0127
N=> ND=> N7=> ND7=> N27=> ND27=> N127=> D127=> 0127
N=> ND=> DD=> 3D=> 34
N=> ND=> N4=> D4 =>34
N=> ND=> NDD=> DDD=> 5DD=> 56D=> 568
N=> ND=> N8=> ND8=> N68=> D68=> 568
解析
文法结构分析：
文法G6的非终结符N的产生式为N→D或ND，D代表单个数字（0-9）。核心思路是通过递归扩展N，生成多个数字的组合。
- 语言L(G6)：由于N可以递归生成任意多个D，因此语言是所有非空数字字符串（即至少一个数字）。
- 最左/最右推导：最左推导每次替换最左非终结符，最右推导每次替换最右非终结符，需注意推导过程中非终结符的扩展顺序。
第（1）题
语言L(G6)：
- N通过
N→ND递归生成多个D，最终每个D替换为具体数字。 - 因此，语言是所有由数字组成的非空字符串，即
L(G6) = {a | a ∈ ∑⁺, ∑ = {0,1,2,...,9}}。
第（2）题
句子0127
最左推导
N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0127
关键：每次扩展最左N，逐步增加D的数量，最后替换为具体数字。
最右推导
N ⇒ ND ⇒ D D ⇒ DND ⇒ D D D ⇒ D1D ⇒ D12D ⇒ D127 ⇒ 0127
关键：每次扩展最右N，优先替换右侧非终结符。
句子34
最左推导
N ⇒ ND ⇒ D D ⇒ 3 D ⇒ 34
最右推导
N ⇒ ND ⇒ N4 ⇒ D4 ⇒ 34
句子568
最左推导
N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 5DD ⇒ 56D ⇒ 568
最右推导
N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 568