# Is it possible to eliminate the unit rules in this?

S -> aA | bC | CC | a | b | C
A -> B
B -> S
C -> A | S


It looks like its going to loop so it would be endless replacing the unit rule....

• We prefer that you do research to try to answer your own question, before asking. Doing a websearch on "context-free grammar eliminate unit rules" turns up resources that describe how to eliminate unit rules, including en.wikipedia.org/wiki/…. If your question is answered in standard resources (e.g., Wikipedia) and can be found through websearch, you probably haven't done enough research before asking here -- there's little point in us repeating information that's already readily available in standard sources. – D.W. Dec 13 '16 at 23:18

## 2 Answers

You could remove A,B,C and replace all instances of them in the rule S, with S.

• So what will happen to the C in S? Will it just disappear? – Euel Domingo Dec 13 '16 at 20:14
• S --> aS | bS | a | b – Logan Leland Dec 13 '16 at 20:15
• S -> aA | bC | CC A -> B B -> S | epsilon C -> A | S – Euel Domingo Dec 13 '16 at 20:16
• Also the CFG you provided at the top can terminate. There are just redundant rules. – Logan Leland Dec 13 '16 at 20:17
• This was the original... – Euel Domingo Dec 13 '16 at 20:17

You can always eliminate unit rules. In fact, every context-free grammar can be massaged to one in Chomsky normal form, and there are several algorithms doing that. Their treatment of unit rules is more subtle than what you suggest.