New Finite Automata Corresponding to Semiextended Regular Expressions

摘要

A semiextended regular expression is a regular expression having an intersection operation. It is known that a regular expression of length 777 can be transformed into a nondeterministic finite automaton of at most 2m states; however, if the semiextended regular expression is to be transformed into an NFA, the number of stales will increase exponentially because of the intersection operation. In this paper, we propose a new model called a partially input-synchronized alternating finite automaton and show that a semiextended regular expression can be transformed into a partially input-synchronized alternating finite automaton of at most 2m states. Yamamoto applied this result to the membership problem of semiextended regular expressions.