JUCS - Journal of Universal Computer Science 27(4): 324-340, doi: 10.3897/jucs.66330
Regular Expressions with Lookahead
expand article infoMartin Berglund‡, Brink van der Merwe‡, Steyn van Litsenborgh‡
‡ Stellenbosch University, Stellenbosch, South Africa

Corresponding author: Steyn van Litsenborgh ( steyn.van.l@gmail.com )

© Martin Berglund, Brink van der Merwe, Steyn van Litsenborgh.
This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use.
Citation: Berglund M, van der Merwe B, van Litsenborgh S (2021) Regular Expressions with Lookahead. JUCS - Journal of Universal Computer Science 27(4): 324-340. https://doi.org/10.3897/jucs.66330
Open Access
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).

Keywords
Regular expressions, Lookahead expressions, Boolean automata