上下文无关文法G的四元组（N，T，P，S)中，S表示（），P表示（）。

语言L（G）={| m≥n ≥0 } 的上下文无关文法中的产生式包括：S→aSb， ，和S→ε

语言L(G)={| n ＞=0 } 的上下文无关文法可以描述成： G1[S]: S→aSb | ε

在如下上下文无关文法G中：stmt-sequence→stmt;stmt-sequence|stmtstmt→s哪些是终结符号？()

Astmt-sequence

Bstmt

Cs

D;

A.1型(上下文有关)文法

B.2型(上下文无关)文法

C.定义标识符的3型(正规)文法

D.0型文法

程序设计语言包括()等几个方面，它的基本成分包括()。Chomsky(乔姆斯基)提出了形式语言的分层理论，他定义了4类文法：短语结构文法、上下文有关文法、上下文无关文法和正则文法。一个文法可以用一个四元组G=(∑，V，S，P)表示，其中，∑是终结符的有限字符表，V是非终结符的有限字母表，S(∈V)是开始符号，P是生成式的有限非空集。

在短语文法中，P中的生成式都是α→β的形式，其中α∈(C)，β∈(∑∪V)*。在上下文有关文法中，P中的生成式都是α₁A_α→α₂βα₂的形式，其中A∈()，β∈(∑∪V)*，β≠ε。在上下文无关文法中，P中的生成式的左部∈()。

供选择的答案：

若文法G定义的语言是无限集，则文法必然是()。

A上下文无关文法

B正规文法

C二义性文法

D递归文法

为下列文法选择最准确的答案：

文法G[S]属于(52)：

S→CD Ab→bA

C→aCA Ba→aB

C→bCB Bb→bB

AD→aD C→ε

BD→bD D→ε

Aa→bD

L(G)={ww|w∈{a，b}*}

文法G[P]属于(53)：

P→0A|1B|0

A→A|1B|OP

B→1B|1|0

文法G[I]属于(54)：

I→IT

I→1

T→IT

T→dT

T→1

T→d

其中，1表示a～z中的任意一个英文字母，d表示0～9中的任意一个数字。

A．1型(上下文有关)文法

B．1型(上下文无关)文法

C．定义标识符的3型(正规)文法

D．0型文法

为下列文法选择最准确的答案：

文法G[S]属于(12)：

S→CD Ab→bA

C→aCA Ba→aB

C→bCB Bb→bB

AD→aD C→s

BD→bD D→c

Aa→bD

L(G)={ww|w∈{a,b)*)

文法G[冈属于(13)：

P→0A|1B|O

A→0A|1B|0P

B→1B|1|0

文法G[1]属于(14)：

I→1T

I→1

T→1T

T→dT

T→1

T→d

其中，1表示a～z中的任意一个英文字母，d表示0～9中的任意一个数字。

A．1型(上下文有关)文法

B．2型(上下文无关)文法

C．定义标识符的3型(正规)文法

D．0型文法

二义文法不是上下文无关文法。()

1. 文法G＝({A,B,S},{a,b,c},P,S), 其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 2. 文法G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 3. 考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？ 4. 给出生成下述语言的二型文法： (1) {anbn | n ＞=0 } (2) { ambn | m≥n ≥0 } (3) {uawb | u,w ∈{a,b}*∧|u|=|w| } (4) { anbm | n≥2m ≥0 } (5) { anbm | n ≥ 0, m ≥ 0,3n≥m≥2n } (6) {wwR|w∈{a,b}*，wR 表示w的逆} (7) {uvwvR|u,v,w∈{a,b}+=1 } 5. 给出生成下述语言的三型文法： (1) {an | n ＞=0 } (2) { anbm | n,m＞=1 } (3) {anbmck | n,m,k＞=0 }