Glushkov's construction algorithm

In computer science theory, particularly formal language theory, the Glushkov Construction Algorithm (GCA) transforms a given regular expression into an equivalent, nondeterministic finite automaton (NFA). It thus forms avcn dhvn, which transforms a finite automaton into a regular expression. The automaton obtained by the Glushkov's construction is the same as the one obtained by Thompson's construction algorithm once their ε-transition is removed.

Construction

The construction creates, given a regular expression $e$, a nondeterministic automaton which accepts the language $L(e)$ accepted by $e$. The construction uses four steps:

1.- Linearisation of the expression. Each letter of the alphabet appearing in the expression are renamed, so that each letters occurs at most once in the new expression. Let $A$ be the old alphabet and let $B$ be the new one.

2a.- Computation of the sets $P(e')$, $D(e')$, and $F(e')$, where $e'$ is the linearized version of $e$. The first, $P(e')$, is the set of letters which occurs as first letter of a word of $L(e')$, the second, $D(e')$, is the set of letters which can ends a letter of $L(e')$. The last one is the set of pairs of letters which can occurs in words of $L(e')$, that is, the set of factors of length two of the words of $L(e')$. Those sets are mathematically defined by

$P(e')=\{a\in B\mid aB^{*}\cap L(e')\neq \emptyset \}$, love people

et $F(e')=\{u\in B^{2}\mid B^{*}uB^{*}\cap L(e')\neq \emptyset \}$. They are computed by induction over the structure of the expression, as explained below, but they are a function of the language and not of the expression.

2b.- Computation of the set $\Lambda (e')$ which contains the empty-word if this word belongs to $L(e')$, and is the empty-set otherwise. Formally

$\Lambda (e')=\{\varepsilon \}\cap L(e')$, where $\varepsilon$ is the empty-word.

3.- Computation of the local language, as defined by $P(e')$, $D(e')$, $F(e')$ and $\Lambda (e')$. By definition, the local language defined by the sets $P$, $D$, and $F$ is the set of words which begin by a letter of $P$, ends by a letter of $D$, and whose factors of length 2 belongs to $F$; that is, it is the language:

$L=(PA^{*}\cap A^{*}D)\setminus A^{*}(A^{2}\setminus F)A^{*}$,

potentially with the empty word.

The computation of the automaton for the local language denoted by this linearised expression, is, formally, Glushkov's construction. The construction of the automaton can be done using classical construction operation: concatenation, interesection and itering an automaton.

4.- Erasing the linearisation, giving to each letter of $B$ the letter of $A$ it used to be.

Example

Automate par construction de Gluskkov - version linéaire

Automate par construction de Gluskkov - version finale

Let us consider the rational expression

$e=(a(ab)^{*})^{*}+(ba)^{*}$.

1.- The linearized version is

$e'=(a_{1}(a_{2}b_{3})^{*})^{*}+(b_{4}a_{5})^{*}$.

The letters have been linearized by appending an indice 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

$P(e')=\{a_{1},b_{4}\}$, $D(e')=\{a_{1},b_{3},a_{5}\}$ and $F(e')=\{a_{1}a_{2},a_{1}a_{1},a_{2}b_{3},b_{3}a_{1},b_{3}a_{2},b_{4}a_{5},a_{5}b_{4}\}$.

The empty word belongs to the language, hence $\Lambda (e')=\{1\}$.

3.- The automaton of the local language

$L'=P'B^{*}\cap B^{*}D'\setminus B^{*}(B^{2}\setminus F')B^{*}$

contains an initial state, denoted 1, and a state for each of the 5 letters of the alphabet $B=\{a_{1},a_{2},b_{3},b_{4},a_{5}\}$. There is a transition from 1 to the two states of $P'$, a transition from $a$ to $b$ if $ab$ is in $F'$, and the three states of $D'$ are final, and such is the state 1. All transitions to a letter $b$ have as label the letter $b$.

4.- Obtening the automaton for $L(e)$ by deleting the indices.

Computation of the set of letters

The computation of the sets $P$, $D$, $F$ and $\Lambda$ is done inductively over the expression. We must give the values for 0, 1 (the symbols for the empty language and the singleton language containing the empty-word), the letters and the results of the operations $+,\cdot ,*$.

1.- For $\Lambda$, one has

$\Lambda (0)=\emptyset ,\Lambda (1)=\{1\}$, and $\Lambda (a)=\emptyset$ for all letters $a$,

then

$\Lambda (e+f)=\Lambda (e)\cup \Lambda (f),\Lambda (e\cdot f)=\Lambda (e)\cdot \Lambda (f)$ and then $\Lambda (e^{*})=\{1\}$

2.- For $P$, one has

$P(0)=P(1)=\emptyset$ and $P(a)=\{a\}$ for each letters $a$,

then

$P(e+f)=P(e)\cup P(f),P(e\cdot f)=P(e)\cup \Lambda (e)P(f)$ and finally $P(e^{*})=P(e)$.

The same formulas are also correct for $D$, apart from the product where

$D(e\cdot f)=D(f)\cup D(e)\Lambda (f)$.

3.- For the set of factors of length 2, one has

$F(0)=F(1)=F(a)=\emptyset$ for all letters $a$,

then

$F(e+f)=F(e)+F(f),F(e\cdot f)=F(e)\cup F(f)\cup D(e)P(f)$ and finally $F(e^{*})=F(e)\cup D(e)F(e)$.

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

Properties

The obtained automaton is non-deterministic, and it has many state as the number of letters of the rational expression, plus one. Furthermore, it has been shown that Glushkov's automaton is the same than 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 function, in particular by the commands grep of Unix. Similarly, XML's specification also use those constructions; for more efficiency, regular expression of a certain kind, called deterministic expression have been studied.