On the Synthesis of Finite-State Machines from Samples of Their Behavior
- 1 June 1972
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-21 (6) , 592-597
- https://doi.org/10.1109/tc.1972.5009015
Abstract
The Nerode realization technique for synthesizing finite-state machines from their associated right-invariant equivalence relations is modified to give a method for synthesizing machines from finite subsets of their input-output behavior. The synthesis procedure includes a parameter that one may adjust to obtain machines that represent the desired behavior with varying degrees of accuracy and that consequently have varying complexities. We discuss some of the uses of the method, including an application to a sequential learning problem.Keywords
This publication has 9 references indexed in Scilit:
- GRAMMATICAL COMPLEXITY AND INFERENCEPublished by Defense Technical Information Center (DTIC) ,1969
- The theory of sequential relationsInformation and Control, 1966
- Realization of Input-Output Relations by Sequential MachinesJournal of the ACM, 1966
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- Design of Sequential Machines from Their Regular ExpressionsJournal of the ACM, 1961
- Synthesis of Minimal-State MachinesIEEE Transactions on Electronic Computers, 1959
- Linear Automaton TransformationsProceedings of the American Mathematical Society, 1958
- A method for synthesizing sequential circuitsBell System Technical Journal, 1955
- The synthesis of sequential switching circuitsJournal of the Franklin Institute, 1954