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....

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 13 '16 at 23:18

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

  • $\begingroup$ So what will happen to the C in S? Will it just disappear? $\endgroup$ Dec 13 '16 at 20:14
  • $\begingroup$ S --> aS | bS | a | b $\endgroup$ Dec 13 '16 at 20:15
  • $\begingroup$ S -> aA | bC | CC A -> B B -> S | epsilon C -> A | S $\endgroup$ Dec 13 '16 at 20:16
  • $\begingroup$ Also the CFG you provided at the top can terminate. There are just redundant rules. $\endgroup$ Dec 13 '16 at 20:17
  • $\begingroup$ This was the original... $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.