3. Suppose we execute the Chomsky-normal-form conversion algorithm of Section 7.

Question

3. 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 X, 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 BCDE? Identify one of these replacing productions from the list below. c) AY, B

Explanation / Answer

Answer: b) A -> BY1

Explanation: In chomsky normal form conversion algorithm, we replace each production A-> B1B2....Bn to A->B1Y where Y -> B2...B2. We apply the same principle here to replace A->BCODE to A->BY1 where Y1 ->CODE

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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