scientific article; zbMATH DE number 26439

From MaRDI portal
Publication:3984633





Three types of indistinguishable state pairs \((a,b)\) in a Moore automaton were defined by \textit{A. Ádám} and \textit{I. Babcsányi} [Stud. Sci. Math. ( Zbl 0724.68057)(to appear)] depending on the properties of the input words \(p\) satisfying \(\delta(a,p)=\delta(b,p)\). Theorem 1 of the present paper answers the following problem: If \(I\) is a subset of \(\{1,2,3\}\) and \(m(\geq 2)\) is an integer, what is the minimum of states of the automata \({\mathcal A}=(A,X,Y,\delta,\lambda)\) such that (1) \({\mathcal A}\) has an indistinguishable state pair of type \(i\) exactly if \(i\in I\) and (2) the number of output signs occurring actually in \({\mathcal A}\) equals \(m\). Theorem 2 states that the partition of \(A\) induced by the output function \(\lambda\) is a congruence if \({\mathcal A}\) is an automaton for which minimum holds in Theorem 1. In the last section a special type of congruences (assigned to state pairs) is studied.












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3984633)