On identification of synchronous sequential machines

✍ Scribed by C.L. Sheng; S.R. Das

• Publisher: Elsevier Science
• Year: 1972
• Tongue: English
• Weight: 436 KB
• Volume: 8
• Category: Article
• ISSN: 0005-1098
• DOI: 10.1016/0005-1098(72)90054-4

✦ Synopsis

For a completely specified strongly connected synchronous sequential machine, the problem of constructing the input-output sequences that will be sufficient to identify the machine, given its flow table, is first studied in this paper. An adaptive procedure is suggested, which constructs the identifying sequences of the machine in successive segments. A necessary condition for an input sequence to be able to identify a machine is that the sequence must lead the machine through all the state transitions. To find such an input sequence of minimal length, a matrix approach is finally proposed in the paper. The modified transition diagram (MTD), modified transition matrix (MTM), and higher-order modified transition matrix are defined, and their relevant properties are studied, which are used to find the required sequence of minimal length.