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) = {anbm|n,m>0}
请给出产生语言为{anbn|n>=1}的文法
G3(S):S→aSb,S→ab
请给出产生语言为{ambn|1<=n<=m<=2n}的文法
G4(S):
S→ab|aab
S→aSb|aaSb
从递归的角度理解