Abstract (EN):
There are many different onstrutions when onverting regular expressions to finite automata. In this paper we fous on the prefix automaton, APre, introdued by Yamamoto in 2014. We present two different methods for the onstrution of APre. First, an indutive one, based on a system of expression equations. A seond one using an iterative funtion for omputing the states and transitions. We establish relationships between APre and other onstrutions, suh as the position automaton, partial derivative automaton and their double reversal (dual) ounterparts. We study the average size of these onstrutions, both experimentally and from an analyti ombinatoris point of view. Finally, we extend the onstrution of the prefix automaton to regular expressions with intersetion and show that the relationships with the other automaton onstrutions also hold for these expressions.
Language:
English
Type (Professor's evaluation):
Scientific
No. of pages:
36