Ok, your notion of walking a graph is not incorrect, but there's a MUCH simpler way to look at your problem: combinations. You basically have a stream of token

Ok, your notion of walking a graph is not incorrect, but there's a MUCH simpler way to look at your problem: combinations. You basically have a stream of tokens (x), and some of these tokens (C) are contractible. In other words, they have alternate forms. So a sentence is something like this: x1 x2 x3 C1 x4 x5 C2 x6 x7 x8 x9 C3 Now, break it up like so, where the contractible word is at the end of each segment, and create the alternate forms: 1a) x1 x2 x3 C1 // C1 is "do not" 1b) x1 x2 x3 C1b // C1b is "don't" 2a) x4 x5 C2 // C2 is "he has" 2b) x4 x5 C2b // C2b is "he's" and so on. Now just find all the combinations of the above segments. 1a 2a, 1a 2b, 1b 2a, 1b 2b. This may look like a nested-loop thing but it's far easier to do it recursively. I have code that does this in Perl, if you want it. I was thinking of translating it to Ruby as an exercise but it looks like I'm too busy for that right now. I suggest you take a look at SICP some day. Writing algorithms like this will be second nature once you grok those techniques.