文法(G)和语言(L)

1.设文法G₂(S):

S->AB

A->aA|a

B->bB|b

G₂(S)产生的语言是什么？

解：L(G₂)={aⁿbⁿ|n≥1}

 

2.请给出产生语言为{aⁿbⁿ|n≥1}的文法

解：G₃(S)：

　　S->ab|aSb

3.上下文无关文法

　一个四元数组G=(VN,VT,S,P)

　　　　VN:非空有限的非终结符集合

　　　　VT:非空有限的终结符集

　　　　S：开始符号

　　　　P：产生式集合

　　　　其中，VN∩VT=∅，S∈VN