Question

Question 1

Consider the following grammar G:

S ➝ A B C | A C | A | B

A ➝ a B

B ➝ b C | a

C ➝ c D

D ➝ d A

Recall that a non-terminal A is reachable if there is a derivation starting from S in which A appears: S ⇒* x A y holds for some x and y which are sequences of terminals and non-terminals (possibly empty). For example, if there are only two rules S → a A and B → a , then A is reachable because S ⇒ a A is a derivation starting from S in which A appears. On the other hand B is not reachable because there is no derivation starting from S in which B appears. Which of the following are the reachable symbols of the grammar G above?

a) A, B, C, D, and S -- Correct Answer

b) S only

c) None of the above

d) A, B, and C only

e) A, B, and S only

Question 2

Consider the following grammar G:

           

S ➝ A B C | A C | A | B

A ➝ a B

B ➝ b C | a

C ➝ c D

D ➝ d A

Recall that a non-terminal A is useful if there is a derivation of a string of terminals starting from S in which A appears: S ⇒* x A y ⇒* w holds for some x and y which are sequences of terminals and non-terminals (possibly empty) and some w which is a sequence of terminals (possibly empty). For example, if there are only three rules S → a A, A → B and B → a , then A is useful because S ⇒ a A ⇒ a B ⇒ a a is a derivation of the sequence of terminals a a starting from S and in which A appears. If A is not useful, then we say that it is useless. Which of the following are the useless symbols of the grammar G above?

a) All non-terminals are useless

b) A, C, and D only

c) D only

d) None of the above -- Correct Answer  

e) C and D only

Can someone explain the concept and how to come up with the answers to these questions?

Answer 1