views:

39

answers:

1

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.

+1  A: 

Not sure this is possible. If A can produce output a, then either B contains a directly or contains b and b' shorter than a that generate a. The same argument then applies to b (and b') - it is either in A directly or there exist a' and a'' shorter than b in A that generate b. Iterate this argument and eventually you get to a point where the individual elements are length 1, so you can't break them down further, and you must have equal elements in both A and B.

Simon D
Yup. I also think that this is not possible. I just thought of the Euclidean algorithm for division as opposed to the conventional division of being two different algorithms but does exactly the same thing. Or am I right pointing this out?
neilmarion
Not quite - Euclidean algorithm gives GCD of two different numbers, here we've got one element and we're trying to break it down differently. More like finding two different prime factorisations of the same number. But proofs are similar I suspect.
Simon D