McNaughton and Yamada algorithm

Difficulty

Average 50%

Contents

The algorithm of McNaughton and Yamada follows the next steps. Given a automaton To not states, and whose states are numbered from 1 to not, we give an expression for the languages composed of the words which label the paths of i To j, for any couple i, j. This expression is built by induction using a condition on the paths. This condition states that the paths only pass through certain authorized states.

Our automaton having not states, so we focus on building a regular expression for each of not×not languages THE_{s, s'} = { w∈X * | s.w = s'} formed by all the words that send a state s any on another state s'. If we succeed, the language recognized by the automaton will be the value of a finite union of regular expressions and therefore of a regular expression.

The idea is to proceed step by step by taking into account an increasing number of intermediate states between s and s'. The states being assumed to be numbered from 0 to not, we start with no intermediate state, then only s₀, then s₀ and s₁, then s₀, s₁ and s₂, etc.

We notice THE_{s, s'}^(k) is the expression for the set of words which label paths from s to s' and whose intermediate vertices are less than or equal to k. The starting vertices s and ending s' are not intermediate, so they are not constrained to be less than or equal to k.

We build the THE_{s, s'}^(k) by induction on k, starting with k = 0, and ending with k = n. When k = n, the constraint on k is no longer a restriction, and THE_{s, s'}^(k)=THE_{s, s'} if s ≠ s', and ε +THE_{s, s}^(not)=THE_{s, s}.

For k = 0, since the vertices are numbered starting from 1, the constraint simply expresses that there is no intermediate vertex. The only paths are transitions from s to s' (we ignore a path of length 0 in state s).

We therefore have with s = p and s' = q:

For induction, we consider a path from s to s' whose intermediate vertices are smaller than k. Two cases are then possible:

the intermediate vertices are smaller than k-1, then the label is in THE_{s, s'}^(k-1)
the path goes through state k. We then decompose the path into parts whose intermediate vertices are smaller than k-1. For this, we consider each occurrence of the vertex k in this path: between two consecutive occurrences, the intermediate vertices are smaller than k-1. We then have the formula with s = p and s' = q: .

There are therefore n + 1 steps. Each of the steps requires the computation of n² expressions, and the size of the expressions themselves increases with k.