Submit your paper 
Download Template JOURNAL DETAIL
Conversion of Parallel Regular Expressions to Non-deterministic Finite Automata using Partial Derivatives
Paper Type  |
Contributed Paper |
Title |
Conversion of Parallel Regular Expressions to Non-deterministic Finite Automata using Partial Derivatives |
Author |
Ajay Kumar and Anil Kumar Verma |
Email |
ajayloura@gmail.com |
|
Abstract: Several techniques like Thompson’s construction, partial derivatives, follow automata and positional automata have been proposed for the conversion of regular expressions to non-deterministic finite automata. Researchers have proposed different methodologies for the conversion of parallel regular expressions to non-deterministic finite automata having the number of states O(2|r|). The aim of the paper is to propose a new approach for the conversion of parallel regular expressions to non-deterministic finite automata. This innovative approach is the generalization of the Antimirov partial derivatives for the conversion of regular expressions to e-free non-deterministic finite automata. The number of states of the non-deterministic finite automaton is reduced from exponential O(2|r|) to polynomial (O(mk+1)), using this novel approach.
|
|
Start & End Page |
1409 - 1418 |
Received Date |
2012-10-18 |
Revised Date |
|
Accepted Date |
2013-05-31 |
Full Text |
Download |
Keyword |
Non-deterministic finite automata, Parallel regular expression, Regular expression, Shuffle operator. |
Volume |
Vol.41 No.5/2 (OCTOBER 2014) |
DOI |
|
Citation |
Kumar A. and Verma A.K., Conversion of Parallel Regular Expressions to Non-deterministic Finite Automata using Partial Derivatives, Chiang Mai Journal of Science, 2014; 41(5/2): 1409-1418. |
SDGs |
|
| View:657 Download:219 | |
Copyrights © Since 2021 All Rights Reserved by Chiang Mai Journal of Science