Chiang Mai Journal of Science

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
SDGs
View:505 Download:149