Eliminating cycles from a grammar
An algorithm to specifically remove cycles can be adapted from the more general algorithm to reduce a grammar to its Chomsky normal form. Specifically, it is the elimination of unit productions, usually abbreviated as UNIT, which is responsible for breaking cycles. Really what follows is a explanation (in fact two, the second being more refined) of how UNIT works, as far as I understand it. The best thing to do is probably to work through the example I gave in the question.

For the S production I have:

S -&gt; Xb | Y

   = Xb | X | a   [replace Y with X | a]

   = Xb | a | c   [replace X with c]


Note that X is replaced with just c and not its full right hand side S | c, presumably to avoid introducing the cyclic unit production S-&gt;S. Note also that the X is effectively moved to the end during the process of eliminating it (I am unable to work out why this should be the case and would love it if someone could tell me).

For the Y production I have:

Y -&gt; X | a

   = a | S | c   [replace X with S | c]

   = a | c | Xb  [replace S with Xb]


Note again that the unit productions are effectively moved to the end during the process of elimination. And again note that S is replaced with Xb and not Xb | Y, presumably for the aforementioned reason of not introducing the cyclic unit production Y-&gt;Y.

For the X production I have:

X -&gt; S | c

   = c | Xb   [replace S with Xb]


Note here that S is replaced with Xb rather than Xb | Y. The reason for this is that the production S-&gt;Y has already been used up, so to speak, and therefore should not be introduced again.

This last step, although it now seems to make sense, confused me at first. In what follows the same algorithm is refined further in order to highlight these kinds of steps. It is also closer to a real implementation. I'll work on a different grammar, this one:

S -&gt; Xb | Y

Y -&gt; X | a

X -&gt; Z | d

Z -&gt; Y | c


I start by dividing up the grammar into non-unit and unit productions:

*******
S -&gt; Xb
Y -&gt; a
X -&gt; d
Z -&gt; c
*******

S -&gt; Y
Y -&gt; X
X -&gt; Z
Z -&gt; Y


I keep the list of non-unit productions fixed, and work on the stack of unit productions. As I create new unit productions, I add them to the top of the stack, effectively replacing the old ones. However, I keep the old ones, they remain above the dashed line (ideally I wish I could cross them out), so I have a record of unit productions that I must not re-introduce. At the same time, as I create new non-unit productions, I put them to one side in a new list and do not pollute the original list. I'll write the stack and list next to each other.

So, I eliminate S-&gt;Y, adding a new non-unit production S-&gt;a and a new unit production S-&gt;X, which I get from applying the unit production Y-&gt;X that can be found lower down in the stack to the right hand side of S-&gt;Y:

1

  S -&gt; Y    S -&gt; a   [from Y-&gt;a in the list of non-unit productions]
  ------
  S -&gt; X             [from applying Y-&gt;X from further down the stack]
  Y -&gt; X     
  X -&gt; Z
  Z -&gt; Y


I'll continue with the process only adding qualifications occasionally when new points crop up...

2

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  ------
  S -&gt; Z          
  Y -&gt; X     
  X -&gt; Z
  Z -&gt; Y


3

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  S -&gt; Z    S -&gt; c   [no more to do, S-&gt;Y has been eliminated already]
  ------
  Y -&gt; X             
  X -&gt; Z
  Z -&gt; Y


4

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  S -&gt; Z    S -&gt; c   
  Y -&gt; X    Y -&gt; d         
  ------
  Y -&gt; Z     
  X -&gt; Z
  Z -&gt; Y


5

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  S -&gt; Z    S -&gt; c   
  Y -&gt; X    Y -&gt; d         
  Y -&gt; Z    Y -&gt; c
  ------
  X -&gt; Z
  Z -&gt; Y


6

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  S -&gt; Z    S -&gt; c   
  Y -&gt; X    Y -&gt; d         
  Y -&gt; Z    Y -&gt; c
  X -&gt; Z    X -&gt; c    
  ------
  X -&gt; Y    
  Z -&gt; Y


7

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  S -&gt; Z    S -&gt; c   
  Y -&gt; X    Y -&gt; d         
  Y -&gt; Z    Y -&gt; c
  X -&gt; Z    X -&gt; c    
  X -&gt; Y    X -&gt; a
  ------
  Z -&gt; Y


7

  S -&gt; Y    S -&gt; a
  S -&gt; X    S -&gt; d      
  S -&gt; Z    S -&gt; c   
  Y -&gt; X    Y -&gt; d         
  Y -&gt; Z    Y -&gt; c
  X -&gt; Z    X -&gt; c    
  X -&gt; Y    X -&gt; a
  Z -&gt; Y    Z -&gt; a
  ------


I hope these steps are clear. Finally, collating we get:

S -&gt; Xb | a | d | c

Y -&gt; a | d | c

X -&gt; d | c | a

Z -&gt; c | a


The astute may notice that the cycle is in fact X-&gt;Z-&gt;Y-&gt;X, S plays no part. It is possible to detect cycles, or more correctly strongly connected components, as a preliminary step, and then apply UNIT only to these components, which would no doubt make for a more efficient algorithm.