A novel algorithm for the conversion of shuffle regular expressions into non-deterministic finite automata

Abstract

Regular expressions with shuffle operators are widely used in diverse fields of computer science. The work presented here investigates the shuffling of regular expressions and their conversion into non-deterministic finite automata. The aim of the paper is to design a novel algorithm for constructing  -free non-deterministic finite automata from the shuffling of regular expressions. Non -deterministic finite automata generated using the proposed approach requires, in the worst case, 2 m+s+1 states. This is a significant improvement over other existing approaches in the literature, where the number of states reaches 2 2(m+u+k+s)-C in the worst case.

Keywords

• parallel regular expression
• non-deterministic
• regular expression
• parallel regular expression
• n on-deterministic finite
• non-deterministic finite automaton
• shuffle operator