文库摘要：

9  10、给定文法：
S∷＝aB | bA
A∷＝aS | bAA | a
B∷＝bS | aBB|b              该文法所描述的语言是什么？
L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。

本文来自文库分享网www.wkfxw.com

P39   11、试分别描述下列文法所产生的语言（文法开始符号为S）：
（1） S∷＝0S | 01
（2） S∷＝aaS | bc
（3） S:: =aSd | aAd
A:: =aAc | bc
（4） S:: =AB
A:: =aAb | ab
B:: =cBd | ε
（1） L(G)＝{0n1| n≥1}；      
（2） L(G)＝{a2nbc | n≥0}；
（3） L(G)＝{aibcjdk | i, j, k≥1, i=j+k-1}；或者 L(G)＝{aj+k-1bcjdk | j, k≥1}；
（4） L(G)＝{anbncmdm | m≥0, n≥1}。

P39 15. 设文法G规则为：
S：：=AB
B：：=a|Sb
A：：=Aa|bB
对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。
（2）baabaab  
（2）                      S