练习1. 文法和语言.docVIP

练习1. 文法和语言 1. 文法: Z → U0 | V1 U → Z1 | 1 V → Z0 | 0 (1) 请写出全部由此文法描述的只含有四个符号的句子. (2) 该文法是 Chomsky 几型文法? Answer： (1) 1010, 0110, 1001, 0101 (2) 3型文法 2. 给定前缀表示的表达式文法 G : (1) E → -EE (2) E → -E (3) E → a (4) E → b (5) E → c 试问 --a-bc 是否 L(G) 的句子?若是,请给出该句子所有可能的分析树;若不是,请说明理由. Answer: --a-bc 是L(G)的句子。所有可能的分析树如下。 (1) (2) (3) 3. 考虑文法： S → ( L ) | a L → L, S | S 写出句型 ( a , ( a , a ) ) 的最左推导和最右推导。 Answer: 最左推导： S(L)(L,S)(S,S)(a,S)(a,(L))(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a)) (2) 最右推导： S(L)(L,S)(L,(L))(L,(L,S))(L,(L,a))(L,(S,a))(L,(a,a))(S,(a,a))(a,(a,a)) 4. 考虑文法： S → aSbS | bSaS |ε 写出句型 abab 的两个最左推导。 Answer: (1) SaSbS abSaSbS abaSbS ababS abab (2) SaSbS abS abaSbS ababS abab 5. 文法 G : P → PaP | PbP | cP | Pe | f 证明文法 G 是二义文法. ** 通过证明句型 f b f b f 存在两棵分析树. Answer: 因为存在两个分析树，所以是二义文法。 两个分析树如下：(1) (2) 6. 文法: S → ( L ) | a L → L , S | S 分析句型: ( L , a , S ), 求：短语、直接短语、句柄、素短语、最左素短语. Answer: 7. 文法: S → a│^│( T ) T → T , S│S 分析句型: ( T , ( ^ , a ) ), 求：短语、直接短语、句柄、素短语、最左素短语. Answer: