Copyright © 2007 Gradiance Corporation.

Gradiance Online Accelerated Learning

CFG's --- Normal Forms

---

---

1.

Here is a grammar, whose variables and terminals are NOT named using the usual convention. Any of R through Z could be either a variable or terminal; it is your job to figure out which is which, and which could be the start symbol. R → ST | UV T → UV | W V → XY | Z X → YZ | T We do have an important clue: There are no useless productions in this grammar; that is, each production is used in some derivation of some terminal string from the start symbol. Your job is to figure out which letters definitely represent variables, which definitely represent terminals, which could represent either a terminal or a nonterminal, and which could be the start symbol. Remember that the usual convention, which might imply that all these letters stand for either terminals or variables, does not apply here.

a)	V must be a variable.
b)	X must be a terminal.
c)	W must be a variable.
d)	R could be a variable or a terminal.

2.

Suppose we execute the Chomsky-normal-form conversion algorithm of Section 7.1.5 (p. 272). Let A → BC0DE be one of the productions of the given grammar, which has already been freed of ε-productions and unit productions. Suppose that in our construction, we introduce new variable Xa to derive a terminal a, and when we need to split the right side of a production, we use new variables Y1, Y2,... What productions would replace A → BC0DE? Identify one of these replacing productions from the list below.

a)	Y1 → Y2C
b)	Y3 → DE
c)	Y3 → Y4D
d)	A → BY2

3.

A unit pair (X,Y) for a context-free grammar is a pair where: X and Y are variables (nonterminals) of the grammar. There is a derivation X =>* Y that uses only unit productions (productions with a body that consists of exactly one occurrence of some variable, and nothing else). For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S Identify all the unit pairs. Then, select from the list below the pair that is NOT a unit pair.

a)

(C,E)

b)

(C,C)

c)

(C,B)

d)

(B,C)

4.	Convert the grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S to an equivalent grammar with no unit productions, using the construction of Section 7.1.4 (p. 268). Then, choose one of the productions of the new grammar from the list below.

a)	A → C1
b)	D → D10
c)	E → 3
d)	A → 3

5.	Here is a context-free grammar: S → AB | CD A → BG | 0 B → AD | ε C → CD | 1 D → BB | E E → AF | B1 F → EG | 0C G → AG | BD Find all the nullable symbols (those that derive ε in one or more steps). Then, identify the true statement from the list below.

a)	C is nullable.
b)	D is not nullable.
c)	A is nullable.
d)	B is not nullable.

6.

Here is a context-free grammar: S → AB | CD A → BG | 0 B → AD | ε C → CD | 1 D → BB | E E → AF | B1 F → EG | 0C G → AG | BD Find all the nullable symbols, and then use the construction from Section 7.1.3 (p. 265) to modify the grammar's productions so there are no ε-productions. The language of the grammar should change only in that ε will no longer be in the language.

a)	E → AF | B1 | F
b)	D → BB | E | B | B
c)	E → AF | B1 | F | 1
d)	C → CD | C

7.

For the grammar: S → AB | CD A → BC | a B → AC | C C → AB | CD D → AC | d Find the generating symbols. Recall, a grammar symbol is generating if there is a deriviation of at least one terminal string, starting with that symbol. Eliminate all useless productions --- those that contain at least one symbol that is not a generating symbol. In the resulting grammar, eliminate all symbols that are not reachable --- they appear in no string derived from S. In the list below, you will find several statements about which symbols are generating, which are reachable, and which productions are useless. Select the one that is FALSE.

a)	d is generating.
b)	D is not reachable.
c)	a is not reachable.
d)	a is not generating.