Consider the CFG given below and find Null and Null-able transitions (if any) al

Question

Consider the CFG given below and find Null and Null-able transitions (if any) also remove these transitions to give new CFG

S ---- > ABB | CC | ABC | AC
A --- > a | ?
B --- > b | C
C --- > ab | ?

[Here ? means null string, as in CFG’s we use ? for indicating null string instead of ^ sign]

Explanation / Answer

Null transitions: A -> ? B -> ? C -> ? Nullable Transitions: (those which can generate null but take more than 1 step) 1.S -> ABB 2. S->CC 3. S -> ABC 4. S -> AC 5. B -> C To understand how I got the answer above, consider, for example S-> ABB. This can generate ? in the following manner S-> ABB -> BB (using A->?) -> CB (using B->C) -> B (using C->?) -> C (using B->C) -> ? (using C->?) Similarly for others.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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