Transforming a Single-Valued Transducer Into a Mealy Machine

Abstract

This article deals with the transformation of a single-valued finite transducer into a Mealy machine. The following results are obtained: (1) Let M be a single-valued real-time (or “letter-to-word”) transducer with n states, input alphabet Σ, and output alphabet Δ which is equivalent to some Mealy machine M′. Then, M can be effectively transformed into such an M′ having at most 2^(n+1) · min{#Σ, #Δ}^(n−1) states. A similar result holds if M is not real time. As an important side effect three “Mealy” properties are obtained which characterize the fact that the given transducer M is equivalent to some Mealy machine. (2) The upper bound in result (1) improves to 2^n − 1 if M is known to be a letter-to-letter transducer. (3) For every integer t ⩾ 2 and every odd integer n ⩾ 3 there is a single-valued real-time transducer M with n states and input and output alphabets of cardinality t such that M is equivalent to some Mealy machine M′ and every such M′ has at least t^((n−1)/2) states. (4) If t = 3, then result (3) holds true with letter-to-letter transducers rather than real-time transducers and with a lower bound of 2^((n−1)/2). (5) It is a PSPACE-complete problem to decide whether or not a given single-valued transducer M is equivalent to some Mealy machine. The problem remains PSPACE-complete if M is known to be a letter-to-letter transducer.