theory - Proof through Number of Derivation Steps -

theory - Proof through Number of Derivation Steps -

given g = {a, b, c, d}, {s, x, y}, s, {s->xy, x->axb, x->ab, y->cyd, y->cy, y->cd}}

prove |w|c-|w|d+|w|a≥|w|b

|w|a how many 'a's there in string. makes sense there more (or same amount of) 'c's 'd's there no production rule makes d without making c while 'c's can made without 'd's using y->cy. need formally prove using induction on number of derivation steps , have been trying day. help appreciated.

theory proof automata formal-languages induction