Figure 1.
Figure 2.
Figure 3.
Figure 4.
Figure 5.
Figure 6.
Figure 7.
Figure 8.
Figure 9.
Figure 10.
Figure 11.
Figure 12.
Figure 13.
Figure 14.
Figure 15.
Figure 16.
Figure 17.
Figure 18.
Figure 19.
Figure 20.
Figure 21.
Figure 22.
Example Input-Output Traces_
| Trace # | Input | Output |
|---|---|---|
| 1 | 000000 | 000000 |
| 2 | 000001 | 000001 |
| 3 | 000101 | 000100 |
| 4 | 010011 | 010001 |
| 5 | 100010 | 100000 |
| 6 | 111000 | 101000 |
| 7 | 110101 | 100100 |
| 8 | 111110 | 101010 |
State transition table that represents the operation of the non-deterministic automaton in Figure 7 as an incompletely specified 3 × 3 function_
| Present State Inputs Q1Q2In (ABC) | Next State Outputs Q′1Q′2Out (PQR) |
|---|---|
| 000 | 0XX |
| 001 | 010 |
| 010 | 00X |
| 011 | 1X1 |
| 100 | 1X1 |
| 101 | 1XX |
| 110 | 1XX |
| 111 | 00X |
State transition table for a simple non-deterministic machine_
| Present State (PS) | Next State (NS) |
|---|---|
| S0 | S1 |
| S1 | S2 |
| S2 | S0 |
| S3 | S0, S1, S2 |
State Transition Table that represents the operation of the automaton in Figure 8 as a completely specified 3 × 3 function_
| Present State Inputs Q1Q2In (ABC) | Next State Outputs Out Q′1Q′2Out (PQR) |
|---|---|
| 000 | 011 |
| 001 | 010 |
| 010 | 000 |
| 011 | 101 |
| 100 | 111 |
| 101 | 100 |
| 110 | 110 |
| 111 | 001 |
Input-Output Trace for a machine that detects a 1 in the third from last symbol of a string_
| Trace # | Input | Output |
|---|---|---|
| 1 | 0000 | 0000 |
| 2 | 1000 | 0001 |
| 3 | 000101 | 000000 |
| 4 | 011011 | 000001 |
| 5 | 011100 | 000001 |
| 6 | 1110001 | 0000000 |
| 7 | 1111001 | 0000001 |
| 8 | 111110111 | 000000000 |
| 9 | 000001000 | 000000001 |
| ‥ | ……… | ……… |
Original function versus final function f(A,B,C) after QAS application_
| Inputs (ABC) | Original Outputs (PQR) | Final Outputs (PQR) |
|---|---|---|
| 000 | 0XX | 011 |
| 001 | 010 | 010 |
| 010 | 00X | 000 |
| 011 | 1X1 | 101 |
| 100 | 1X1 | 111 |
| 101 | 1XX | 100 |
| 110 | 1XX | 110 |
| 111 | 00X | 001 |