The following questions are based on the following grammar: S -> AB | b A -> aA

Question

The following questions are based on the following grammar:

S -> AB | b

A -> aA | ?

B -> CD

C -> bA | AA

D -> AB | BC

For each question, to get credit you must check all and only the symbols that have

the stated property.

(a) Check all and only the nullable symbols.

I) S

II) A

III) B

IV) C

V) D

(b) Check all and only the variables that derive a terminal string.

I) S

II) A

III) B

IV) C

V) D

Now, modify the grammar to eliminate all productions that involve one or more symbols that do not derive a terminal string.

(c) Check all and only the variables that appear in some sentential form derived from S using this modified grammar.

I) S

II) A

III) B

IV) C

V) D

----------------------------------------------------------

I understand a) (A and C) and b) (S, A, and C). However, I need some help with c). Your help is much appreciated! =)

Explanation / Answer

S -> AB | b
A -> aA | ?
B -> CD
C -> bA | AA
D -> AB | BC

Let's take
S -> AB

A means 0/more a's
So, let's see all possibilities for B

B -> CD which can be
B -> bAD | AAD after substituting for C and which can be
B -> bAAB | bABC | AAAB | AABC

Everytime it involves B in above 4 which means that it doesn't produce any terminal symbols. So, we can remove B.

When we remove B, D isn't used anymore. So, remove D as well. C isn't used anywhere. So, remove C.

S -> AB also has to be removed because B is no longer used.

Grammar now is
S -> b
A -> aA | ?

Now, A isn't used. Remove it as well.

Finally the grammr is
S -> b

Answer is just option I)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.