Regular Expressions with Lookahead
Martin Berglund, Brink van der Merwe, Steyn van Litsenborgh
Abstract
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).
Topics & Concepts
Concatenation (mathematics)Regular expressionRegular languageNondeterministic finite automatonDFA minimizationAutomatonDeterministic finite automatonFinite-state machineDiscrete mathematicsQuantum finite automataKleene algebraState (computer science)Computer scienceStar (game theory)MathematicsTheoretical computer scienceAlgorithmCombinatoricsAutomata theoryProgramming languageMathematical analysissemigroups and automata theoryDNA and Biological ComputingCoding theory and cryptography