1. How can I prove that the output sequence of Mealy Moore Machine is a Regular Language ?
  2. And what if transition outputs more than one character ? How can we prove for this case that the language in (1) and (2) are same ?

Can I do something like this -

enter image description here

The right side one is Mealy Machine. So can I prove like making a machine in left with transitions using output sequence of Mealy Machine ?


By discarding the input-letters you only consider the output language of the respective Mealy automaton. Effectively you obtain a finite state automaton that recognizes the output language and because it is a finite state automaton, which may be non-deterministic, the language it accepts is regular.

The length of the output of a Mealy-transition is irrelevant as you may have for example$aa\in\Gamma$, where $\Gamma$ denotes the output alphabet of a Mealy automaton.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.