Berry-Sethi method

The Berry-Sethi method (after Gérard Berry and Ravi Sethi ; also Glushkov construction , after Viktor Michailowitsch Gluschkow ) is an algorithm for converting a regular expression into a nondeterministic finite automaton .

First, the regular expression is transferred to a tree structure . The nodes correspond to the rules of the regular expression (concatenation , transitory closure and union ). The leaves represent the elements of the input alphabet in the regular expression, i.e. exactly the characters from which valid words can be composed. All further calculations take place with the help of this form of representation. ${\ displaystyle \ cdot}$ ${\ displaystyle ^ {*}}$ ${\ displaystyle \ mid}$

If one imagines a point before the beginning at the root of the syntax tree to the tree wandering , so all words can the regular expression are generated successively. With the help of this point the finite automaton is constructed. The time complexity of the procedure is . ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

method

Find empty [r] for all nodes r of the tree. This is a post-order possible DFS (DFS: depth-first search, depth-first search ).
Find first [r] for all nodes r of the tree. This is possible with a post-order DFS.
Find next [r] for all nodes r of the tree. This is possible with a pre-order DFS.
Find last [r] for all nodes r of the tree. This is possible with a post-order DFS.
Integration:
1. The states of the machine are: ${\ displaystyle \ {\ bullet e \} \ cup \ {i \ bullet \ mid {\ mbox {i is sheet}} \}}$
2. The start status of the machine is: ${\ displaystyle \ bullet e}$
3. The final states of the machine are:
  1. ${\ displaystyle last [e]}$ if and ${\ displaystyle empty [e] = false}$
  2. ${\ displaystyle \ {\ bullet e \} \ cup last [e]}$ if ${\ displaystyle empty [e] = true}$
4. The transitions of the machine are:
  1. ${\ displaystyle (\ bullet e, a, i \ bullet)}$ , if and is labeled with , and ${\ displaystyle i \ in first [e]}$ ${\ displaystyle i}$ ${\ displaystyle a}$
  2. ${\ displaystyle (i \ bullet, a, i '\ bullet)}$ , if and is labeled with . ${\ displaystyle i '\ in next [i]}$ ${\ displaystyle i '}$ ${\ displaystyle a}$

The symbol marks the point that wanders around the tree. The resulting finite automaton is generally nondeterministic and can therefore still be made deterministic by the power set construction. ${\ displaystyle \ bullet}$

literature

Gérard Berry, Ravi Sethi: From regular expressions to deterministic automata. In: Theoretical Computer Science. 48, 1986, ISSN 0304-3975 , pp. 117-126.
Viktor M. Glushkov: The abstract theory of automata. In: Russian Mathematical Surveys. 16, 1961, ISSN 0036-0279 , pp. 1-53.
Anne Brüggemann-Klein : Regular expressions into finite automata . In: Theoretical Computer Science 120, 1993, pp. 197-213. doi : 10.1016 / 0304-3975 (93) 90287-4