Hello everyone!
Can you give me 2 different grammars which outputs the same set of words?
Illustration:
Given a grammar A and B over the alphabet {0,1}, if grammar A can produce the word 0101001, grammar B could as well. If grammar B can produce 0101111 then grammar A could as well. And if grammar A can't produce 01001 then B can neither.
But the thing here is that grammar A and B are different from each other i.e. they use totally different algorithms. Then the set of outputs they produce is not just a proper subset of the other one. Meaning to say their corresponding set of outputs must have the same cardinality. Probably they are of different complexity class, but it doesn't matter. If you may, I would greatly appreciate it if you'll give me grammars over the alphabet {0,1} just like the classical Turing machine.