题目

考虑下面上下文无关文法:S—>SS*|SS+|a(1)表明通过此文发如何生成串aa+a*,并为该串构造推导树。(2)该文法生成的语言是什么?

考虑下面上下文无关文法:

S—>SS*|SS+|a

(1)表明通过此文发如何生成串aa+a*,并为该串构造推导树。

(2)该文法生成的语言是什么?

题目解答

答案

答:(1)S=>SS*=>SS+S*=>aS+S*=>aa+S*=>aa+a*

S=>SS*=>SS*S*=>SS*S*S*=>…=>S(S*)=>Sa*(S*)=>aa*a*

(S*)=>…=>S(a*)=>SS+(a*)=>SS+S+(a*)=>SS+S+S+(a*)=>…=>S(S+)(a*)=>a(S+)(a*)=>aa+(S+) (a*)=>aa+a+(S+) (a*)=>a(a+)(a*)

所以该文发生成的语言是:

L1={ a(a+)(a*)|n,m>=1}

解析

考查要点：本题主要考查上下文无关文法的推导过程及语言描述能力。
解题核心思路：

  1. 推导过程：通过逐步应用产生式规则，从起始符号S推导出目标字符串。
  2. 语言描述：分析文法的生成规则，归纳出所有可能生成的字符串的结构特征。
    破题关键点：
  • 推导步骤需严格遵循产生式，注意符号替换的顺序。
  • 语言结构需体现文法中*和+的组合方式，以及最终以a结尾的特点。

第（1）题

推导过程

  1. 初始符号：S
  2. 第一次展开：应用S → SS*，得到SS*
  3. 第二次展开：左侧S应用S → SS+，得到SS+ S*
  4. 第三次展开：左侧S应用S → a，得到aS+ S*
  5. 第四次展开：左侧S应用S → a，得到aa+ S*
  6. 第五次展开：右侧S应用S → a，得到aa+ a*

推导树

        S
      / | \
     S  *  (空)
    / | \
   S  +  (空)
  /     \
 a      S
          \
           a

第（2）题

语言描述：
文法生成的语言由至少一个a开始，后跟任意数量的a通过+或*连接的组合，且+和*的组合至少各出现一次。
形式化描述：
$L = \{ a \cdot (a^+)^n \cdot (a^*)^m \mid n, m \geq 1 \}$