1

We have the following automata $A$:

Automata A

My task is to find automata $B$ and $C$ such that both of them admit a homomorphism to $A$, but $B$ is not homomorphic to $C$ and vice versa.

So far, we know that both $B$ and $C$ have to be automata accepting the same language as $A$. Furhermore, it is clear that it is language of binary words with the even number of zeroes.

My definition of automata homomorphism is the same as in here.

gebruiker
  • 6,154
ABC
  • 11
  • Just to be sure, what is your definition of homomorphism of automata? – J.-E. Pin Mar 23 '16 at 03:23
  • Crosspost with http://cstheory.stackexchange.com/questions/34144/automata-homomorphism – J.-E. Pin Mar 23 '16 at 03:43
  • The definition of homomorphism given in your link does not say anything about final states and thus it is not sufficient to conclude that B and C should accept the same language. – J.-E. Pin Mar 24 '16 at 05:18

0 Answers0