题目
令文法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
解析
步骤 1：确定文法G6的语言L(G6)
文法G6由两个产生式组成：N→D|ND 和 D→0|1|2|3|4|5|6|7|8|9。N可以推导出一个或多个D，而D代表数字0到9。因此，L(G6)是所有由数字0到9组成的非空字符串的集合。
步骤 2：给出句子0127的最左推导和最右推导
最左推导：从左到右逐步替换非终结符N，直到得到句子0127。
最右推导：从右到左逐步替换非终结符N，直到得到句子0127。
步骤 3：给出句子34的最左推导和最右推导
最左推导：从左到右逐步替换非终结符N，直到得到句子34。
最右推导：从右到左逐步替换非终结符N，直到得到句子34。
步骤 4：给出句子568的最左推导和最右推导
最左推导：从左到右逐步替换非终结符N，直到得到句子568。
最右推导：从右到左逐步替换非终结符N，直到得到句子568。
文法G6由两个产生式组成：N→D|ND 和 D→0|1|2|3|4|5|6|7|8|9。N可以推导出一个或多个D，而D代表数字0到9。因此，L(G6)是所有由数字0到9组成的非空字符串的集合。
步骤 2：给出句子0127的最左推导和最右推导
最左推导：从左到右逐步替换非终结符N，直到得到句子0127。
最右推导：从右到左逐步替换非终结符N，直到得到句子0127。
步骤 3：给出句子34的最左推导和最右推导
最左推导：从左到右逐步替换非终结符N，直到得到句子34。
最右推导：从右到左逐步替换非终结符N，直到得到句子34。
步骤 4：给出句子568的最左推导和最右推导
最左推导：从左到右逐步替换非终结符N，直到得到句子568。
最右推导：从右到左逐步替换非终结符N，直到得到句子568。