SKEDSOFT
Error-correcting DFAs: Consider another experiment that shows the value of tool-assisted debugging of machines. In this experiment, a DFA has to be designed to recognize all strings that are a Hamming distance of 2 away from the set of strings denoted by the regular expression (0101) . For instance, 010101 and 010110 are a Hamming distance of 2 apart, as are 010111 and 000110.
Definition: (Hamming Distance) Given two strings V1 and V2, of equal length and over {0, 1}∗, they are a Hamming distance of d apart if they differ in exactly d positions. The DFA we are to design can be regarded as an error-correcting DFA which corrects two-bit errors. We shall derive this DFA using two distinct approaches, each time by following two different lines of logic:
- The first approach will be to develop a cyclic DFA that performs transitions between states I, A, B, C, F, and back to A upon seeing 01010. However, upon seeing any erroneous symbol—for instance, seeing a 1 in state I, it goes to a cycle at a lower “stratum” labeled with states A1, B1, etc. This is presented in Figure 10.12.
- Another approach will be to write a regular expression that captures all possible zero-bit errors, all possible one-bit errors, and all possible two-bit errors.
We shall find the minimal DFAs corresponding to these constructions. If correctly performed, we must obtain isomorphic minimal DFAs, again serving to verify our construction methods. We discuss these constructions in the following sections.
DFA constructed using error strata
Fig. 10.12. A DFA that has two error strata implementing all strings that are a Hamming distance of 2 away from the language (0101) The DFA corresponding to the use of error-correcting strata is captured in Figure 10.12. By running the command perl fa2grail.perl h2 > h2fa,2 we convert this ASCII input into a grail representation. Following that, we apply the command
cat h2fa | fmdeterm | fmmin | perl grail2ps.perl - > h2fa.ps
The result is shown in Figure 10.13 on the left-hand side.
DFA constructed through regular expressions: A regular expression that captures all possible zero, one, and two-bit errors is in Figure 10.14. We have added spaces and newlines, as well as comments beginning with “--” to enhance the readability of the above RE. We then perform the command sequence:
cat h2re | retofm | fmdeterm | fmmin | perl grail2ps.perl - > h2fa1.ps
The result is shown in Figure 10.13 on the right-hand side. Contrasting it with the other DFA in this figure, we can see that barring node numberings as well as the layout (under the control of the ‘dot’ drawing package), these DFAs are isomorphic.
