109

urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891

JUCS - Journal of Universal Computer Science

jucs

0948-695X 0948-6968

Journal of Universal Computer Science

10.3897/jucs.66330

66330

Research Article

F.1 - COMPUTATION BY ABSTRACT DEVICES F.4.3 - Formal Languages F.4 - MATHEMATICAL LOGIC AND FORMAL LANGUAGES Topic F - Theory of Computation

Regular Expressions with Lookahead

Berglund

Martin

1 van der Merwe

Brink

1 van Litsenborgh

Steyn

steyn.van.l@gmail.com 1

Stellenbosch University, Stellenbosch, South Africa

Stellenbosch University

Stellenbosch

South Africa

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

Academic editor:

2021

28 04 2021

27 4 324 340 C5FA43B8-3335-56E1-99D2-E6A286E8F280 28 10 2020 08 03 2021

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.

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).