![]() Brzozowski (1964) used derivatives to construct finite automata the state for expression E has a transition under a to the state for the derivative of E by a. ![]() Correspondingly, if the input string is generated by a regular expression E, then the derivative of E by a generates the remaining input after a leading a is stripped. When a finite automaton makes a transition under input symbol a, a leading a is stripped from the remaining input. Derivatives of regular expressions correspond to state transitions in finite automata. The elegant algorithm for constructing a finite automaton from a regular expression is based on 'derivatives of' regular expressions the efficient algorithm is based on 'marking of' regular expressions. The main theorem allows an elegant algorithm to be refined into an efficient one.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |