Question

写一个文法使其语言是奇数集S→A丨CAC→CB丨CA→1丨3丨5丨7丨9C→0丨1丨2丨3丨4丨5丨6丨7丨8丨9B→1

Answer 1

首先分析题意,本题是希望构造一个文法,由它产生的句子是奇数,并且不以0开头,也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾.如果数字只有一位,则1、3、5、7、9就满足要求,如果有多位,则要求第1位不能是0,而中间有多少位,每位是什么数字（必须是数字）则没什么要求,因此,我们可以把这个文法分3部分来完成.分别用3个非终结符来产生句子的第1位、中间部分和最后一位.引入几个非终结符,其中,一个用作产生句子的开头,可以是1－9之间的数,不包括0,一个用来产生句子的结尾,为奇数,另一个则用来产生以非0整数开头后面跟任意多个数字的数字串,进行分解之后,这个文法就很好写了.