Patent Document ID: 9690688
Application ID: 13779898
Patent Flag: 1

Claim One:
1. A method comprising: receiving a regular expression; creating a deterministic finite automaton (DFA) based on the regular expression; and using the DFA, by a processor, to generate an elementary string set, wherein each string of the elementary string set matches the regular expression, wherein using the DFA to generate the elementary string set comprises: adding a start state of the DFA to the state queue, adding an empty string to a string queue, and processing each state in the state queue, wherein processing a state in the state queue comprises: extracting the state from the state queue, extracting a string from the string queue, incrementing a counter associated with the state, updating a data structure to store the counter, in an instance in which the state is terminal, adding the extracted string to the elementary string set, retrieving a set of symbols that cause a transition from the state to another state in the DFA, and for each symbol of the set of symbols, updating the state queue and the string queue based on the symbol, wherein the data structure comprises a tree structure, each state being a key of the tree structure and the associated counter being a value of the tree structure associated with the key, and wherein (a) a second state of the plurality of states is defined by transitioning a first state of the state queue to the second state using a symbol, and (b) wherein the second state comprises no more than two instances of the symbol; and wherein (a) each string in the elementary string set will loop no more than twice while matching the regular expression, (b) the string set is maximal having no more than one string with same properties matching the regular expression, and (c) the elementary string set is generated to test software that uses the regular expression.