Glushkov's construction algorithm

In computer science theory – particularly formal language theory – Glushkov's construction algorithm, invented by Victor Mikhailovich Glushkov, transforms a given regular expression into an equivalent nondeterministic finite automaton (NFA). Thus, it forms a bridge between regular expressions and nondeterministic finite automata: two abstract representations of the same class of formal languages. A regular expression may be used to conveniently describe an advanced search pattern in a "find and replace"–like operation of a text processing utility. Glushkov's algorithm can be used to transform it into an NFA, which furthermore is small by nature, as the number of its states equals the number of symbols of the regular expression, plus one. Subsequently, the NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. The latter format is best suited for execution on a computer.

From another, more theoretical point of view, Glushkov's algorithm is a part of the proof that NFA and regular expressions both accept exactly the same languages; that is, the regular languages. The converse of Glushkov's algorithm is Kleene's algorithm, which transforms a finite automaton into a regular expression. The automaton obtained by Glushkov's construction is the same as the one obtained by Thompson's construction algorithm, once its ε-transitions are removed.

Construction

Given a regular expression e, the Glushkov Construction Algorithm creates a non-deterministic automaton that accepts the language [math]\displaystyle{ L(e) }[/math] accepted by e. The construction uses four steps:

Step 1

Linearisation of the expression. Each letter of the alphabet appearing in the expression e is renamed, so that each letter occurs at most once in the new expression [math]\displaystyle{ e' }[/math]. Glushkov's construction essentially relies on the fact that [math]\displaystyle{ e' }[/math] represents a local language [math]\displaystyle{ L(e') }[/math]. Let A be the old alphabet and let B be the new one.

Step 2a

Computation of the sets [math]\displaystyle{ P(e') }[/math], [math]\displaystyle{ D(e') }[/math], and [math]\displaystyle{ F(e') }[/math]. The first, [math]\displaystyle{ P(e') }[/math], is the set of letters which occurs as first letter of a word of [math]\displaystyle{ L(e') }[/math]. The second, [math]\displaystyle{ D(e') }[/math], is the set of letters that can end a word of [math]\displaystyle{ L(e') }[/math]. The last one, [math]\displaystyle{ F(e') }[/math], is the set of letter pairs that can occur in words of [math]\displaystyle{ L(e') }[/math], i.e. it is the set of factors of length two of the words of [math]\displaystyle{ L(e') }[/math]. Those sets are mathematically defined by

[math]\displaystyle{ P(e')=\{x\in B\mid xB^*\cap L(e')\ne\emptyset\} }[/math],

[math]\displaystyle{ D(e')=\{y\in B\mid B^*y\cap L(e')\ne\emptyset\} }[/math],

[math]\displaystyle{ F(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\} }[/math].

They are computed by induction over the structure of the expression, as explained below.

Step 2b

Computation of the set [math]\displaystyle{ \Lambda(e') }[/math] which contains the empty word if this word belongs to [math]\displaystyle{ L(e') }[/math], and is the empty set otherwise. Formally, this is [math]\displaystyle{ \Lambda(e')=\{\varepsilon\}\cap L(e') }[/math], where [math]\displaystyle{ \varepsilon }[/math] denotes the empty word.

Step 3

Computation of automaton recognizing the local language, as defined by [math]\displaystyle{ P(e') }[/math], [math]\displaystyle{ D(e') }[/math], [math]\displaystyle{ F(e') }[/math], and [math]\displaystyle{ \Lambda(e') }[/math]. By definition, the local language defined by the sets P, D, and F is the set of words which begin with a letter of P, end by a letter of D, and whose factors of length 2 belong to F, optionally also including the empty word; that is, it is the language:

[math]\displaystyle{ L'=(PB^*\cap B^*D) \setminus B^*(B^2\setminus F)B^* \cup \Lambda(e') }[/math].

Strictly speaking, it is the computation of the automaton for the local language denoted by this linearised expression that is Glushkov's construction.

Step 4

Remove the linearisation, replacing each indexed letter B by the original letter of A.

Example

Automaton constructed by Glushkov's algorithm – linear version

Automaton constructed by Glushkov's algorithm - final version

Consider the regular expression [math]\displaystyle{ e = (a(ab)^*)^* + (ba)^* }[/math].

1. The linearized version is

   [math]\displaystyle{ e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^* }[/math].

   The letters have been linearized by appending an index to them.
2. The sets P, D, and F of the first letters, last letters, and factors of length 2 for the linear expression are respectively

   [math]\displaystyle{ \begin{align} P(e')&=\{a_1,b_4\}\\ D(e')&=\{a_1,b_3,a_5\}\\ F(e')&=\{a_1a_2, a_1a_1, a_2b_3, b_3a_1,b_3a_2,b_4a_5,a_5b_4\} \end{align} }[/math].

   The empty word belongs to the language, hence [math]\displaystyle{ \Lambda(e')=\{ \varepsilon \} }[/math].
3. The automaton of the local language

   [math]\displaystyle{ L'=(PB^*\cap B^*D) \setminus B^*(B^2\setminus F)B^* }[/math]

   contains an initial state, denoted 1, and a state for each of the five letters of the alphabet

   [math]\displaystyle{ B=\{a_1, a_2, b_3, b_4, a_5\} }[/math].

   There is a transition from 1 to the two states of P, a transition from x to y for [math]\displaystyle{ xy \in F }[/math], and the three states of D are final, and such is the state 1. All transitions to a letter y have as label the letter y.
4. Obtain the automaton for [math]\displaystyle{ L(e) }[/math] by deleting the indices.

Computation of the set of letters

The computation of the sets P, D, F, and Λ is done inductively over the regular expression [math]\displaystyle{ e' }[/math]. One must give the values for ∅, ε (the symbols for the empty language and the singleton language containing the empty word), the letters, and the results of the operations [math]\displaystyle{ +,\cdot,^* }[/math].

1. For Λ, one has

   [math]\displaystyle{ \Lambda(\emptyset)=\emptyset }[/math],

   [math]\displaystyle{ \Lambda(\varepsilon)=\{ \varepsilon \} }[/math],

   [math]\displaystyle{ \Lambda(a)=\emptyset }[/math] for each letter a,

   [math]\displaystyle{ \Lambda(e+f)=\Lambda(e)\cup\Lambda(f) }[/math],

   [math]\displaystyle{ \Lambda(e\cdot f)=\Lambda(e)\cdot \Lambda(f) }[/math], and

   [math]\displaystyle{ \Lambda(e^*)=\{ \varepsilon \} }[/math].

2. For P, one has
   [math]\displaystyle{ P(\emptyset)=P(\varepsilon)=\emptyset }[/math],
   [math]\displaystyle{ P(a)=\{a\} }[/math] for each letter a,
   [math]\displaystyle{ P(e+f)=P(e)\cup P(f) }[/math],
   [math]\displaystyle{ P(e\cdot f)= P(e)\cup\Lambda(e)P(f) }[/math], and
   [math]\displaystyle{ P(e^*)=P(e) }[/math].

   The same formulas are also used for D, except for the product where

   [math]\displaystyle{ D(e\cdot f)= D(f)\cup D(e) \Lambda(f) }[/math].

3. For the set of factors of length 2, one has
   [math]\displaystyle{ F(\emptyset)=F(\varepsilon)=F(a)=\emptyset }[/math] for each letter a,
   [math]\displaystyle{ F(e+f)=F(e)\cup F(f) }[/math],
   [math]\displaystyle{ F(e\cdot f)=F(e)\cup F(f)\cup D(e)P(f) }[/math], and
   [math]\displaystyle{ F(e^*)=F(e)\cup D(e)P(e) }[/math].

The most costly operations are the products of sets for the computation of F.

Properties

The obtained automaton is non-deterministic, and it has as many states as the number of letters of the regular expression, plus one. Furthermore, it has been shown that Glushkov's automaton is the same as Thompson's automaton when the ε-transitions are removed.

Applications and deterministic expressions

The computation of the automaton by the expression occurs often; it has been systematically used in search functions, in particular by the Unix grep command. Similarly, XML's specification also uses such constructions; for more efficiency, regular expressions of a certain kind, called deterministic expressions, have been studied.

See also

• Аналитик

External links

• A Unified Construction of the Glushkov, Follow, and Antimirov Automata

• Algorithms and Computation: 14th International Symposium, ISAAC