[deterministic]

Maybe you could have generated random test input, generated the trees, and then converted the trees back to the input, checking if they match?

[nz]

Yeah, that is situation 2 mentioned above. A Chomsky Grammar is also a generator. So it can generate valid inputs, and then turn them into valid outputs -- and it can do the first part stochastically/randomly.