结构推理 用正则文法或者上下文无关文法描述语言:由所有小写英文字母构成,并且开始和结尾都是字母a的所有符号串构成的集合。
【正确答案】本题主要考察用文法描述语言的能力,即描述语言成分(句子)构成规律的方法。引入一个非终结符B表示所有出现在句子中间(非结尾位置)的符号,定义另一个非终结符A表示由任意小写英文字母构成的符号串,定义第3个非终结符S表示文法起始符号。则文法写成如下的形式:
   S→a|aA a
   A→ε|BA
   B→a|b|c|d|e|f|g|h|ij|k|1|m|n|o|p|q|r|s|t|u|v|w|x|y|z
【答案解析】