3.2文法与语言

1、文法生成语言

推导

• 定义：当αAβ直接推导出αγβ，即αAβ⇒αγβ，仅当A→γ是一个产生式，且α,β∈(VT∪VN)*。
  注：按照我的理解是两个字符串的推导。
• 如果α1⇒α2⇒…⇒αn,则我们称这个序列是从α1到αn的一个推导。若存在一个从α1到αn的推导，则称α1可以推导出αn。
• 对文法G(E):E→i | E+E | E*E | (E)
  E⇒(E)⇒(E+E)⇒(i+E)⇒(i+i)
• 从一个串到另外一个串的推导往往不是唯一。
• 下面这个就是一种推导
  
• α1⇒* αn,从α1出发，经过0步或若干步推出αn.
• α1⇒+ αn,从α1出发，经过1步或若干步推出αn.
• α⇒* β ,α=β 或α⇒+ β
• 下面三种都是合理的
  <句子> ⇒* He gave me a book.
  <句子> ⇒+he gave me a book.
  He gave 间接宾语 直接宾语 ⇒+ He gave me 冠词 名词

句型、句子和语言

• 假如G是一个文法，S是它的开始符号。如果S⇒*α，则称α是一个句型。
  比如：<主语><谓语><间接宾语><直接宾语>⇒ *He<谓语><间接宾语><直接宾语>,则称He<谓语><间接宾语><直接宾语>是句型。
• 仅包含终结符的句型是一个句子。
  比如：he gave me a book.是一个句子。
• 文法G所产生的句子的全体是一个语言，记为L(G)。
  L(G) = {α|S⇒+α,α∈VT*}

2、句型和句子练习

请证明(ii+i)是文法G(E):E→i | E+E | EE | (E)的一个句子。
满足下面这两种条件。
S⇒* α，α∈VT*（α要可以被S推导出来，并且a要都是终结符）
证明：
E⇒(E)
⇒(E+E)
⇒(E * E+E)
⇒(i * E+E)
⇒(i * i+E)
⇒(i * i+i)
(i * i+i)是文法G的句子。
E，(E)，(E*E+E)，…,(i * i+i)是句型。

3、文法与语言

设文法G1(A):A→c | Ab,G1(A)产生的语言是什么？

• 以c,开头，后续若干个b
• L(G1) = {c,cb,cbb,…}

设文法G2(S)：S→AB，A→aA | a,B→bB|b,G2(S)产生的语言是什么？

• L(G2) = {aⁿb^m|n,m>0}

请给出产生语言为{aⁿbⁿ|n>=1}的文法

• G3(S):S→aSb,S→ab
  

请给出产生语言为{a^mbⁿ|1<=n<=m<=2n}的文法

• G4(S):
  S→ab|aab
  S→aSb|aaSb
  从递归的角度理解