context-free-grammarcontext-free-language

Simplifying CFG: S -> SS | (S) | ε


Is it possible to simplify even more the next CFG?

S -> SS | (S) | ε

I've removed all the other null and unit productions, but I believe it is possible to simplify it even more.


Solution

  • How about

    S -> (S)S | ε
    

    Does that cover all the bits of the original?

    S -> (S) is covered by the second S being ε

    S -> SS is either two ε, check; or contains at least one pair of parens, check

    Yes, that looks about right. You can choose whether you like (S)S or S(S) better, should work the same.

    Note: not very authoritative, I have only a vague idea what I'm talking about