第2章 形式语言基础

2.2 设有文法G[N]:   N -> D | ND

D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

(1)    G[N]定义的语言是什么?

(2)    给出句子0123和268的最左推导和最右推导。      

解答：

(1)    L(G[N])={(0|1|2|3|4|5|6|7|8|9)⁺} 或L(G[N])={a| a为可带前导0的正整数}

(2)     

0123的最左推导：N Þ ND Þ NDD Þ NDDD Þ DDDD Þ 0DDD Þ 01DD Þ 012D Þ 0123

0123的最右推导：N Þ ND Þ N3 Þ ND3 Þ N23 Þ ND23 Þ N123 Þ D123 Þ 012