Minimal finite-state automaton associated with a sequential circuit

Pierre MOUKELI MBINDZOUKOU

Abstract The tendency in the implementation of the sequential circuits is to specify the behavior of a circuit in the term of a finite automaton. Then to use a tool to transcribe this description in a specification language that will produce a simulation of the circuit before its implementation. This approach deprives the designer of the powerful mathematical tools developed in language theory, allowing significant reductions in complexity in term of the number of states and transitions. The present contribution proposes an approach making it possible to deduce from a sequential circuit specification the associated minimum automaton, the implementation of which allows a substantial reduction in the complexity of said circuit. Algorithms in this sense are proposed to decompile a sequential circuit, to construct the disjunctive canonical form of its transition function by using the canonical monomials composed of the states and input variables, and to deduce a minimal finite automaton. The implementation of this minimal finite automaton will give a less complex circuit as foreseen in the theory of languages. Keywords: regular languages, finite-state automaton, sequential circuit simplification, transition function.

Title:	Minimal finite-state automaton associated with a sequential circuit
Author Name:	Pierre MOUKELI MBINDZOUKOU
Abstract:	Abstract The tendency in the implementation of the sequential circuits is to specify the behavior of a circuit in the term of a finite automaton. Then to use a tool to transcribe this description in a specification language that will produce a simulation of the circuit before its implementation. This approach deprives the designer of the powerful mathematical tools developed in language theory, allowing significant reductions in complexity in term of the number of states and transitions. The present contribution proposes an approach making it possible to deduce from a sequential circuit specification the associated minimum automaton, the implementation of which allows a substantial reduction in the complexity of said circuit. Algorithms in this sense are proposed to decompile a sequential circuit, to construct the disjunctive canonical form of its transition function by using the canonical monomials composed of the states and input variables, and to deduce a minimal finite automaton. The implementation of this minimal finite automaton will give a less complex circuit as foreseen in the theory of languages. Keywords: regular languages, finite-state automaton, sequential circuit simplification, transition function.
Cite this article:	Pierre MOUKELI MBINDZOUKOU , " Minimal finite-state automaton associated with a sequential circuit " , International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), Volume 6, Issue 1, January - February 2017 , pp. 112-123 , ISSN 2278-6856.
Full Text [PDF] Home