-expression without epsilon-transitions.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 -expression without epsilon-transitions.
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
Related Domains:
Dom::BooleanSemiRing, Dom::MaxMinSemiRing, Dom::MaxPlusSemiRing, Dom::MinMaxSemiRing, Dom::MinPlusSemiRing, Dom::RationalExpression, Dom::SemiRing, Dom::WeightedAutomaton
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.