Pitanje o kompajlerima

[satja]

Netko je smislio čudan, nama nepoznat programski jezik X i napisao kompajler za njega u C-u. Potom je u samome X-u napisao kompajler za X i poslao nam njegov source kod, string S. Taj string jedino je što mi znamo.

Pitanje glasi: da li S jednoznačno određuje X? Drugim riječima, ako Mirko i Slavko svaki zasebno, znajući S, napišu u C-u kompajler za X takav da sve štima, podudaraju li se nužno outputi njihovih kompajlera za sve inpute?

Added after 21 minutes:

I dodatno, postoji li algoritam koji na temelju S rekonstruira neki mogući X (što bi značilo da npr. napiše kompajler za njega u C-u)?

[simon11]

Kako se rjesavaju uopce ti zadaci , mora li se, za odgovor ne, za jedinstvenost dati kontraprimjer?

Je li algoritam povezan s automatima?

[excrucio]

Pa da, automati su, ali ne znam točno kako dokazati/opovrgnuti jedno, odnosno drugo.

Valjda kontraprimjer...