Print

Print


Alright, there's definitely a solution there.

I can work these with JFLAP (CYK parse):

S ->  aXb
X -> SX | λ

and

S -> aB
B -> SB | b

The other ones rejected my test string aabababaaababbabbb, namely these:

S -> aB
B -> Sb | b

and

S -> Ab
A -> aS | a

> I doubt there is any way to make this work with actually only one
production rule. But I'll think on it a little more, just in case.

Thanks, this is actually pretty amazing. I don't think I would've figured it out any time soon at all. If there's more where that came from, I'm definitely interested; anyway here's already what I'm going to need.

This grammar shouldn't be as simple as the fundamental one, so it's all looking good.