Moore Automaton

automata-theory

Definition

Moore Automaton

A Moore automaton is a special case of a transducer that is defined by a tuple:

$$\mathcal{M}=(Q,\Sigma ,\Gamma ,\delta ,\gamma ,q_0)$$

where:

• $Q$ is the finite set of states
• $\Sigma$ is the input alphabet
• $\Gamma$ is the output alphabet
• $\delta :Q\times \Sigma \to Q$: is the transition function
• $\gamma :Q\to \Gamma$: is the output function
• $q_0\in Q$ is the initial state

A Moore automaton is a a deterministic automaton that doesn’t have empty word transitions, has an output function, a single initial state, and no explicit accepting states ($F=Q$).

Output Function

Extended Output Function

Extended Output Function

The extended output function ${\gamma }^{\ast }:Q\times {\Sigma }^{\ast }\to {\Gamma }^{\ast }$ is a function that takes a state $q\in Q$ and an input string $x\in {\Sigma }^{\ast }$ and returns the output $y\in {\Gamma }^{\ast }$.

Example

Signal Edge Detector