examples::FreeThompson – set of Thompson automata without epsilon-transitions

examples::FreeThompson(A,S) creates a domain for Thompson automata over the alphabet A and the component semi-ring S after an epsilon-transitions removal process.

The domain element examples::FreeThompson(A,S)(expression) represents the Thompson automaton induced by a rational math-expression without epsilon-transitions.

→ Examples

Creating the Type

examples::FreeThompson(A, S)

FreeThompson(A,S)(expression)

Parameters:

A

an alphabet, i.e., a list of letters

S

a semiring, i.e., a domain of category Cat::SemiRing

expression

a string.

Superdomain

Dom::BaseDomain

Related Domains:

Dom::BooleanSemiRing, Dom::MaxMinSemiRing, Dom::MaxPlusSemiRing, Dom::MinMaxSemiRing, Dom::MinPlusSemiRing, Dom::RationalExpression, Dom::SemiRing, Dom::WeightedAutomaton

Example 1:

Let us consider the set of free Thompson automata defined over the alphabet {a,b} and the semi-ring of rational numbers. Then, we define the set of scalars and the alphabet:

Q:=Dom::Rational:

 

alphabet:=[a,b]:

 

Next the set of free Q-Thompson automata is constructed:

FQ:=examples::FreeThompson(alphabet,Q):

 

Now we create a free Q-Thompson autamaton induced by the writing of a rational Q-expression:

FQ("1/2*(star(a)+star(b))")

+-                                                    -+

| 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |,

+-                                                    -+

 

       +-                                                        -+

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 1/2, 0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 1/2, 0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

   a = |                                                          |,

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       |                                                          |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0, 0, 0, 0, 0, 0  |

       +-                                                        -+

 

       +-                                                        -+  +-   -+

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1/2, 0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  0  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1/2, 0, 0, 0  |  |  2  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  2  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  0  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  2  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  0  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  0  |

   b = |                                                          |, |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  0  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  0  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  1,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  1  |

       |                                                          |  |     |

       |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0, 0, 0  |  |  1  |

       +-                                                        -+  +-   -+

 

As we can obtain large automata by the Thompson construction, it is interesting to minimize them :

(Dom::WeightedAutomaton(Q))::minimization(%)

              +-        -+      +-         -+  +-   -+

+-    -+      |  0, 1/2  |      |  1, -1/2  |  |  1  |

| 1, 0 |, a = |          |, b = |           |, |     |

+-    -+      |  0,  1   |      |  0,   0   |  |  1  |

              +-        -+      +-         -+  +-   -+

 

Changes in MuPAD 4.0

New Function.