@article{Antimirov1996291,
    Abstract = {We introduce a notion of partial derivative of a regular expression and apply it to finite automaton constructions. The notion is a generalization of the known notion of word derivative due to Brzozowski: partial derivatives are related to non-deterministic finite automata (NFA's) in the same natural way as derivatives are related to deterministic ones (DFA's). We give a constructive definition of partial derivatives and prove several facts, in particular: 1. (1) any derivative of a regular expression r can be represented by a finite set of partial derivatives of r; 2. (2) the set of all partial derivatives of r is finite and its cardinality is less than or equal to one plus the number of occurrences of letters from A appearing in r; 3. (3) any partial derivative of r is either a regular unit, or a subterm of r, or a concatenation of several such subterms. These theoretical results lead us to a new algorithm for turning regular expressions into relatively small NFA's and allow us to provide certain improvements to Brzozowski's algorithm for constructing DFA's. We also report on a prototype implementation of our \{NFA\} construction and present several examples.},
    Author = {Antimirov, Valentin},
    File = {antimirov1996 (0) - a - a - k.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Number = {2},
    Pages = {291 - 319},
    Title = {Partial derivatives of regular expressions and finite automaton constructions},
    URL = {//www.sciencedirect.com/science/article/pii/0304397595001824},
    Volume = {155},
    Year = {1996},
    bdsk-url-1 = {http://dx.doi.org/10.1016/0304-3975(95)00182-4},
    bdsk-url-2 = {//www.sciencedirect.com/science/article/pii/0304397595001824},
    date-added = {2017-01-25 16:28:17 +0000},
    date-modified = {2017-01-25 16:28:17 +0000},
    doi = {10.1016/0304-3975(95)00182-4}
}

@article{Antimirov1996291, Abstract = {We introduce a notion of partial derivative of a regular expression and apply it to finite automaton constructions. The notion is a generalization of the known notion of word derivative due to Brzozowski: partial derivatives are related to non-deterministic finite automata (NFA's) in the same natural way as derivatives are related to deterministic ones (DFA's). We give a constructive definition of partial derivatives and prove several facts, in particular: 1. (1) any derivative of a regular expression r can be represented by a finite set of partial derivatives of r; 2. (2) the set of all partial derivatives of r is finite and its cardinality is less than or equal to one plus the number of occurrences of letters from A appearing in r; 3. (3) any partial derivative of r is either a regular unit, or a subterm of r, or a concatenation of several such subterms. These theoretical results lead us to a new algorithm for turning regular expressions into relatively small NFA's and allow us to provide certain improvements to Brzozowski's algorithm for constructing DFA's. We also report on a prototype implementation of our {NFA} construction and present several examples.}, Author = {Antimirov, Valentin}, File = {antimirov1996 (0) - a - a - k.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Number = {2}, Pages = {291 - 319}, Title = {Partial derivatives of regular expressions and finite automaton constructions}, URL = {//www.sciencedirect.com/science/article/pii/0304397595001824}, Volume = {155}, Year = {1996}, bdsk-url-1 = {http://dx.doi.org/10.1016/0304-3975(95)00182-4}, bdsk-url-2 = {//www.sciencedirect.com/science/article/pii/0304397595001824}, date-added = {2017-01-25 16:28:17 +0000}, date-modified = {2017-01-25 16:28:17 +0000}, doi = {10.1016/0304-3975(95)00182-4} }