Un autómata aperiódico de estado finito (también llamado autómata sin contador ) es un autómata de estado finito cuyo monoide de transición es aperiódico .
Un lenguaje regular está libre de estrellas si y solo si es aceptado por un autómata con un monoide de transición finita y aperiódica . Este resultado de la teoría de los autómatas algebraicos se debe a Marcel-Paul Schützenberger . [1] En particular, el autómata mínimo de un lenguaje sin estrellas siempre está libre de contadores (sin embargo, un lenguaje sin estrellas también puede ser reconocido por otros autómatas que no son aperiódicos).
Un lenguaje libre de contadores es un lenguaje regular para el cual hay un entero n tal que para todas las palabras x , y , z y enteros m ≥ n tenemos xy m z en L si y solo si xy n z en L . Otra forma de enunciar el teorema de Schützenberger es que los lenguajes sin estrellas y los lenguajes sin contadores son lo mismo. [ más explicación necesaria ]