Report Number: CSL-TR-75-93
Institution: Stanford University, Computer Systems Laboratory
Title: Sequential circuit output probabilities from regular expressions
Author: Parker, Kenneth P.
Author: McCluskey, Edward J.
Date: June 1975
Abstract: This paper presents a number of methods for finding
sequential circuit output probabilities using regular
expressions. Various classes of regular expressions, based on
their form, are defined and it is shown how to easily find
multistep transition probabilities directly from the regular
expressions. A new procedure for finding steady state
probabilities is given which proceeds either from a regular
expression or a state diagram description. This procedure is
based on the concept of synchronization of the related
machine, and is useful for those problems where
synchronization sequences exist. In the cases where these
techniques can be utilized, substantial savings in
computation can be realized. Further, application to other
areas such as multinomial Markov processes is immediate.