Title :
Parallel Algorithms for Constructing Fellow Automata of Regular Expressions
Author :
Yuqiang, Sun ; Ruimin, Yang ; Yuwan, Gu ; Jing, You
Author_Institution :
Coll. of Comput. & Inf. Technol., Henan Normal Univ., Xinxiang, China
Abstract :
A parallel algorithm for translating regular expression into its Follow automata is proposed in the paper. Firstly, we construct the Thompson automata of a regular expression. Then, the Glushkov automata are achieved by removing xi the path and the equivalent states which have equivalent relations are merged into one. So we can get a smaller finite automata, named Follow automata. Finally the parallel processing of algorithm is described in detail with an example.
Keywords :
automata theory; formal languages; parallel algorithms; Follow automata; Glushkov automata; Thompson automata; parallel algorithm; parallel processing; regular expression translation; Application software; Automata; Databases; Educational institutions; Information science; Information technology; Parallel algorithms; Parallel processing; Pattern matching; Sun; Follow automatata; NFA; parallel algorithm; regular expressions; state;
Conference_Titel :
Database Technology and Applications, 2009 First International Workshop on
Conference_Location :
Wuhan, Hubei
Print_ISBN :
978-0-7695-3604-0
DOI :
10.1109/DBTA.2009.41
