| This project involves stretching and jamming automata and regular expressions. Given a deterministic finite automaton (DFA), we can stretch it by transforming each single transition into two or more sequential transitions, thereby introducing additional intermediate states. For example, an ASCII DFA can be stretched by transforming each single ASCII (8-bit) character transition into two transitions, each of 4-bits. Jamming is the opposite transformation, in which two successive transitions (for example 8-bit) are transformed into a single (in this example 16-bit) transition. The operations on regular expressions are analogous. In this project we will explore ways of implementing stretching and jamming and evaluate the effectiveness of these operations in terms of running time and memory consumption. |