Publication | Open Access
Regular Expressions with Lookahead
16
Citations
0
References
2021
Year
EngineeringPushdown AutomatonEquivalent Boolean AutomataComputational ComplexityWeighted AutomatonFormal VerificationString-searching AlgorithmString ProcessingComputational LinguisticsDescriptional ComplexityLanguage StudiesLogical AutomatonComputer ScienceCombinatorial Pattern MatchingFormal MethodsAutomaton OperationState ComplexityRegular ExpressionsLinguistics
This paper investigates regular expressions which in addition to the standard operators of union, concatenation, and Kleene star, have lookaheads . We show how to translate regular expressions with lookaheads ( REwLA ) to equivalent Boolean automata having at most 3 states more than the length of the REwLA . We also investigate the state complexity when translating REwLA to equivalent deterministic finite automata (DFA).