Regular expressions into finite automata
type: Item
instance of: scholarly article
title: Regular expressions into finite automata
zbMATH Open document ID: 0811.68096
DOI: 10.1016/0304-3975(93)90287-4
author: Anne Brüggemann-Klein
published in: Theoretical Computer Science
publication date: 1994-02-22T00:00:00Z
review text: It is well-known that the regular expressions can be translated into non- deterministic finite automata \((NFA)\) with or without \(\lambda\)- transitions. The standard method first translate a regular expression, in linear time, into an NFA with \(\lambda\)-transitions and then the \(\lambda\)-transitions are eliminated in quadratic time. There is another method, proposed by Glushkov and based on the fact that, if a word is denoted by an expression, it must be possible to spell out that word by tracing an appropriate ``path'' through the expression. It was shown that the Glushkov's method can be described in terms of Brzozowski derivatives and on the other hand this method plays an important role in document processing. In this paper the author shows that the Glushkov automaton associated to a regular expression can be constructed in quadratic time in the size of the expression, and in the case of deterministic expressions the construction can be done in linear time. The result is obtained first for regular expressions in star normal form (also introduced in this paper) and then it is translated to the general case. The paper is directed then on the unambiguity of the regular expressions and it is shown that the weak unambiguity can be tested in quadratic time improving the methods known until now. Finally, some interesting open problems are mentioned.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 501178
zbMATH Keywords: regular expressions
zbMATH Keywords: non-deterministic finite automata
zbMATH Keywords: Glushkov automaton
reviewed by: Ferucio Laurenţiu Ţiplea
describes a project that uses: AWK
MaRDI profile type: Publication
Wikidata QID: Q61458432
full work available at URL: 0304-3975(93)90287-4
OpenAlex ID: W2099540492
cites work: Q3992625
cites work: Q5452362
cites work: Q3036710
cites work: From regular expressions to deterministic automata
cites work: Ambiguity in Graphs and Expressions
cites work: Deterministic regular languages
cites work: Derivatives of Regular Expressions
cites work: THE ABSTRACT THEORY OF AUTOMATA
cites work: Q5579037
cites work: Q5592246
cites work: Q4103466
cites work: Q4040284
cites work: Q4692941
DBLP publication ID: journals/tcs/Bruggemann-Klein93
description: scientific article; zbMATH DE number 501178