Left factor a grammar that doesn't have a left common factor?

Question

I'm working on a question, and it says that I must left factor the following grammar:

A -> A ∪ B | B

B -> B C | C

C -> C* | D

D -> a | b

What I'm stuck on is, isn't this grammar already left factored? Looking at it, I can't see anything explicitly in the form of S -> αβ₁ | αβ₂ , which is the form that my book says left-factoable grammars must take.

Let't take the production rules for B. If it were left factorable, wouldn't it have to take the following form?

B -> C B | C

The only way I could think to factor the production rule for B would be this:

B -> B' C

B' -> B | ϵ

However, this doesn't seem like a valid operation on the production rules for B because the common factor is on the right, not the left. Can someone help me understand this?

Answer 1

Your productions $A \to A \cup B \mid B$ and $B \to B C \mid C$ are left recursive, and have to be factored.