# Eliminating cycles from a grammar

I have the following grammar:

S -> Xb | Y

Y -> X | a

X -> S | c


Here the lowercase letters are terminals.

I have an algorithm to find the cycle in this grammar. It is S->Y->X->S and in fact there is a smaller cycle buried in there, namely S->X->S.

I've tried to devise an algorithm to remove these cycles, without too much thought, but I've come up with nothing.

Any help would be appreciated.

• There are algorithms for eliminating cycles, which you can just run on your grammar. They appear in many textbooks. – Yuval Filmus Jun 7 '17 at 17:49
• More concretely, a grammar in Chomsky normal form or in Greibach normal form doesn't have cycles, so you can look for algorithms for producing these kinds of grammars. – Yuval Filmus Jun 7 '17 at 19:22
• The accepted answer is wrong at the first transformation. It should end up with S -> Sb | cb | a | c. The final grammar is wrong as well and of course. It can only generate six words, db | ca | aa | a | d | c. – Apass.Jack May 2 at 20:34

There are known algorithms to convert context-free grammars to Chomsky normal form. Grammars in Chomsky normal form don't contain cycles, and indeed one of the steps is removing cycles. One such algorithm is described in Wikipedia.

Some people have graciously implemented one of these algorithms online, for example Matthew Peveler. Running his tool on your grammar, we get the following result (try!):

\begin{align*} &S \to XA \mid a \mid c \\ &Y \to a \mid c \mid XA \\ &X \to c \mid XA \\ &A \to b \end{align*} Undoing one step, we get a simpler grammar, which might be what you're looking for: \begin{align*} &S \to Xb \mid a \mid c \\ &Y \to a \mid c \mid Xb \\ &X \to c \mid Xb \\ \end{align*} The online tool is provided with source code which you can examine, though textual descriptions (available in Wikipedia and elsewhere) will probably be easier to follow.

Starting with

S -> Xb | Y

Y -> X | a

X -> S | c


I would rewrite it as

Step 1: get rid of Y

S -> Xb | X | a
X -> S | c


Step 2: get rid of X

S -> Sb | cb | c | a


You get a grammar with the immediate left recursion which can be eliminated further if you need to.

But if you need a systematic way to eliminate cycles, then you need to use algorithms that transform a CFG to normal form.

• Right, yes. And this is what I missed in my digging today. All of the material I found, see the references here for example, seemed to skirt around the issue, mainly I think because eliminating cycles plays only a bit part in eliminating left recursion. Now I have this lead I am up and running, thank you. I will throw away my cack-handed attempt at an algorithm in my question tomorrow. Thanks again. – James Smith Jun 7 '17 at 21:14
• I had another look at your answer. I'm grateful, but I don't see how you can simply remove the Y production. Or, rather, it seems common sense to remove it, and yet other algorithms would not. Perhaps the answer is that eliminating immediate left recursion would introduce another production which would effectively take the place of the missing Y production. – James Smith Jun 8 '17 at 16:50

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

For the X production I have:

X -> 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->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 -> Xb | Y

Y -> X | a

X -> Z | d

Z -> Y | c


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

*******
S -> Xb
Y -> a
X -> d
Z -> c
*******

S -> Y
Y -> X
X -> Z
Z -> 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->Y, adding a new non-unit production S->a and a new unit production S->X, which I get from applying the unit production Y->X that can be found lower down in the stack to the right hand side of S->Y:

1

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


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

2

  S -> Y    S -> a
S -> X    S -> d
------
S -> Z
Y -> X
X -> Z
Z -> Y


3

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


4

  S -> Y    S -> a
S -> X    S -> d
S -> Z    S -> c
Y -> X    Y -> d
------
Y -> Z
X -> Z
Z -> Y


5

  S -> Y    S -> a
S -> X    S -> d
S -> Z    S -> c
Y -> X    Y -> d
Y -> Z    Y -> c
------
X -> Z
Z -> Y


6

  S -> Y    S -> a
S -> X    S -> d
S -> Z    S -> c
Y -> X    Y -> d
Y -> Z    Y -> c
X -> Z    X -> c
------
X -> Y
Z -> Y


7

  S -> Y    S -> a
S -> X    S -> d
S -> Z    S -> c
Y -> X    Y -> d
Y -> Z    Y -> c
X -> Z    X -> c
X -> Y    X -> a
------
Z -> Y


7

  S -> Y    S -> a
S -> X    S -> d
S -> Z    S -> c
Y -> X    Y -> d
Y -> Z    Y -> c
X -> Z    X -> c
X -> Y    X -> a
Z -> Y    Z -> a
------


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

S -> Xb | a | d | c

Y -> a | d | c

X -> d | c | a

Z -> c | a


The astute may notice that the cycle is in fact X->Z->Y->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.

• I am glad that I don't have to worry about eliminating null productions, because the definition of what they are seems to vary a little from place to place and I can guarantee that there are none to start with. I am also going to go out on a limb and say that what results will be in CNF although I can't quite elucidate why. – James Smith Jun 8 '17 at 19:47
• I should take back part of the above comment (I do not have the necessary privileges to alter it). This is not CNF, since only UNIT has been applied. For me, however, there is no advantage in reducing the grammar completely to CNF and therefore UNIT suffices. – James Smith Jun 9 '17 at 8:50

You can treat productions as equations, and solve them accordingly.

Taking up where @fade2black left off, we have

\begin{align} S &= Sb | cb | c | a\\ &= Sb | (cb|c|a) \end{align}

The solution to

$$X = X \alpha | \beta$$

is

$$X = \beta \alpha^*$$

So

\begin{align} S &= (cb|c|a)b^* \end{align}

• I've written out my answer now, I think I have it, but thanks anyway. Also, I'm not sure I follow your reasoning but I'm interested. Do you have a reference? – James Smith Jun 9 '17 at 13:06
• @JamesSmith My go-to source is Regular Expressions and Finite Machines by John Conway. The grammar is left-linear, not right-linear, but the solution is still a regular expression. You'll find the above as Theorem 3 in Chapter 3: Regular Events and Expressions. – Thumbnail Jun 9 '17 at 13:46
• I'll look it up some time maybe, thank you. – James Smith Jun 9 '17 at 13:50