Search code examples
automata

Build grammar to the language

L = {a^i b^j c^k | not(i=j=k)}

Hint : describe L as a union of other languages

I have been trying to do this for like a week now and just can't. Can anyone help me understand?

Edit :

Is it right to say :

(i≠j or j≠k) or (i≠j and j≠k and i≠k)

Solution

  • is it right to say : (i≠j or j≠k) or (i≠j and j≠k and i≠k)

    It's not wrong to say that, but that's more than you need to say. Really, all you need to say is the first part:

    (i≠j or j≠k)

    The second part couldn't possibly be true if the first part weren't already true anyway. From here, we can further break this down:

    i < j or i > j or j < k or j > k

    This is the union of four pretty basic context free languages. If you get grammars G1, G2, G3 and G4 for them with start symbols S1, S2, S3 and S4, respectively, you can add a new start symbol S and productions S -> S1 | S2 | S3 | S4 to get a grammar for their union.