In this chapter we decribe how to create an aaa transducer.
The aaa package provides a method to represent transducers in GAP.
‣ Transducer( m, n, P, L ) | ( operation ) |
Returns: A transducer.
For two positive integers m, and n, a dense list of dense lists of integers P, and a dense list of dense lists of dense lists of integers L, such that P and L have the same size, and each of their elements have size equal to m, the operation Transducer(m, n, P, L) returns a transducer with input alphabet [0 .. m - 1], output alphabet [0 .. n - 1], transition function P, and output function L. If p abstractly represents the transition function of the transducer, then P has the property that p(currentstate, inputletter - 1) = P[currentstate][inputletter], where currentstate is an integer from [1 .. Size(P)], and inputletter is a positive integer representing the word [inputletter - 1]. Similarly, if l abstractly represents the output function of the transducer, then L has the property that l(currentstate, inputletter - 1) = L[currentstate][inputletter], where currentstate, and inputletter are as before.
gap> T := Transducer(2, 2, [[2, 3], [2, 3], [2, 3]], > [[[], []], [[0], [0]], [[1], [1]]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 3 states.>
‣ TransducerFunction( T, word, m ) | ( operation ) |
Returns: A list.
For a transducer T, a dense list word, and a positive integer m such that it is a state of the transducer, the operation TransducerFunction(T, word, m) returns a list containing the word obtained when word is read by T from state m, and the state that is reached after reading word from state m.
gap> T := Transducer(2, 2, [[1, 2], [2, 1]], [[[0], []], [[1], [0, 1]]]);; gap> TransducerFunction(T, [0, 1, 0], 1); [ [ 0, 1 ], 2 ]
‣ TransitionFunction( T ) | ( operation ) |
‣ OutputFunction( T ) | ( operation ) |
Returns: A list.
For a transducer T, the operation TransitionFunction(T) displays the list representing the transition function of T, and the operation OutputFunction(T) displays the list representing the output function of T.
gap> T := Transducer(2, 2, [[1, 2], [2, 1]], [[[0], []], [[1], [0, 1]]]);; gap> TransitionFunction(T); [ [ 1, 2 ], [ 2, 1 ] ] gap> OutputFunction(T); [ [ [ 0 ], [ ] ], [ [ 1 ], [ 0, 1 ] ] ]
‣ InputAlphabet( T ) | ( operation ) |
‣ OutputAlphabet( T ) | ( operation ) |
Returns: A list.
For a transducer T, the operation InputAlphabet(T) returns the list representing the input alphabet of T, and the operation OutputAlphabet(T) returns the list representing the output alphabet of T.
gap> P := Transducer(2, 3, [[1, 2], [2, 1]], [[[0], [2]], [[1], [0, 1]]]);; gap> InputAlphabet(P); [ 0, 1 ] gap> OutputAlphabet(P); [ 0 .. 2 ]
‣ NrInputSymbols( T ) | ( operation ) |
‣ NrOutputSymbols( T ) | ( operation ) |
Returns: A positive integer.
For a transducer T, the operation NrInputSymbols(T) returns the number of symbols of the input alphabet of T, and the operation NrOutputSymbols(T) returns the number of symbols of the output alphabet of T.
gap> T := Transducer(2, 3, [[1, 2], [2, 1]], [[[0], []], [[1], [2, 1]]]);; gap> NrInputSymbols(T); NrOutputSymbols(T); 2 3
‣ States( T ) | ( operation ) |
Returns: A list of integers.
For a transducer T, the operation States(T) returns a list representing the set of states of the transducer T.
gap> T := Transducer(2, 2, [[1, 2], [2, 1]], [[[0], []], [[1], [0, 1]]]);; gap> States(T); [ 1, 2 ]
‣ NrStates( T ) | ( operation ) |
Returns: A positive integer.
For a transducer T, the operation NrStates(T) returns the number of states of the transducer T.
gap> T := Transducer(2, 2, [[1, 2], [2, 1]], [[[0], []], [[1], [0, 1]]]);; gap> NrStates(T); 2
‣ IdentityTransducer( n ) | ( operation ) |
Returns: A transducer
For a positive integer n, the operation IdentityTransducer(n) returns a transducer with input and output alphabet size n. The transducer has 1 state and when a word is read from this state, the same word is output.
gap> T := IdentityTransducer(3); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 1 state.> gap> EqualTransducers(T, Transducer(3, 3, [[1, 1, 1]], [[[0], [1], [2]]])); true
‣ AlphabetChangeTransducer( m, n ) | ( operation ) |
Returns: A transducer
For two positive integers m, n, the operation AlphabetChangeTransducer(m, n) returns a transducer with input alphabet size m and output alphabet size n. This transducer is never degenerate and always induces a homeomorphism h_{m, n} from the cantor space of infinite words over the alphabet of size mto the cantor space of infinite words over the alphabet of size n. These homeomorphisms have the property that the composit of h_{a, b} with h_{b, c} is equal to h_{a, c} for all a, b, and c.
gap> T := Transducer(2, 4, [[1, 2], [1, 3], [1, 1]], > [[[0], []], [[1], []], [[2], [3]]]);; gap> EqualTransducers(T, AlphabetChangeTransducer(2, 4)); true gap> T:= Transducer(2, 2, [ [ 3, 1 ], [ 2, 3 ], [ 1, 1 ] ], > [ [ [ 1 ], [ 0 ] ], [ [ 1 ], [ 1 ] ], [ [ 0 ], [ 1 ] ] ]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 3 states.> gap> TConjugate := T^AlphabetChangeTransducer(2, 3); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 6 states.> gap> TConjugate2 := TConjugate^AlphabetChangeTransducer(3, 2); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 12 states.> gap> TConjugate2 = T; true
‣ RandomTransducer( m, n ) | ( operation ) |
Returns: A transducer
For positive integers m, n, the operation RandomTransducer(m, n) returns a random transducer with input and output alphabet of size m and n states. All transition functions are equally likely. For each state and letter pair (q, l), the chances that the word written when l is read from state q has length 0, 1, 2, 3, ... are 1/4, 3/8, 3/16, 3/32 ... respectively. Each word of a fixed length has the same chance of being written.
gap> RandomTransducer(3, 5); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 5 states.>
In this section we explain the different transducer attributes that the aaa package can compute.
‣ IsDegenerateTransducer( T ) | ( attribute ) |
Returns: true or false.
For a transducer T, the attribute IsDegenerateTransducer(T) returns true if T is a degenerate transducer, and false otherwise.
gap> T := Transducer(2, 2, [[2, 2], [1, 3], [2, 1]], [[[0], [0]], > [[0, 1, 0, 0, 0, 1], []], [[0, 0, 0], [0]]]);; gap> IsDegenerateTransducer(T); false gap> T := Transducer(3, 3, [[1, 2, 2], [3, 2, 3], [1, 3, 3]], [[[2, 2], > [2, 2, 2, 2, 1, 1, 0, 1], [2, 0]], [[], [0, 1], [2]], [[1], [1], []]]);; gap> IsDegenerateTransducer(T); true gap> T := Transducer(3, 3, [[1, 1, 3], [3, 1, 1], [2, 3, 2]], > [[[0, 2, 2], [0], [2, 2]], [[], [0], [0]], [[2], [1, 2], []]]);; gap> IsDegenerateTransducer(T); true gap> T := Transducer(5, 3, [[1, 1, 1, 1, 1], [1, 1, 1, 1, 2]], > [[[0], [1], [2, 0], [2, 1], [2, 2]], [[1], [2, 0], [2, 1], > [2, 2, 0], [2, 2]]]);; gap> IsDegenerateTransducer(T); false
‣ IsInjectiveTransducer( T ) | ( attribute ) |
Returns: true or false.
For a transducer T, with initial state 1, the attribute IsInjectiveTransducer(T) returns true if T is an injective transducer, and false otherwise.
gap> T := Transducer(2, 2, [[2, 4], [3, 6], [3, 2], [5, 7], [5, 4], > [6, 6], [7, 7]], [[[0], []], [[0, 1], [1, 0, 1]], [[1, 1, 1], > [1, 0]], [[0, 0], [0, 1, 0]], [[0, 0, 0], [1, 1]], [[0], [1]], > [[0], [1]]]);; gap> IsInjectiveTransducer(T); false gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], > [0], [1]], [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]);; gap> IsInjectiveTransducer(f); true
‣ IsSurjectiveTransducer( T ) | ( attribute ) |
Returns: true or false.
For a transducer T, with initial state 1, the attribute IsSurjectiveTransducer(T) returns true if T is a surjective transducer, and false otherwise.
gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], > [0], [1]], [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]);; gap> IsSurjectiveTransducer(f); true
‣ IsBijectiveTransducer( T ) | ( attribute ) |
Returns: true or false.
For a transducer T, the attribute IsBijectiveTransducer(T) returns true if T is a bijective transducer, and false otherwise.
gap> T := Transducer(2, 2, [[2, 4], [3, 6], [3, 2], [5, 7], [5, 4], [6, 6], > [7, 7]], [[[0], []], [[0, 1], [1, 0, 1]], [[1, 1, 1], [1, 0]], [[0, 0], > [0, 1, 0]], [[0, 0, 0], [1, 1]], [[0], [1]], [[0], [1]]]);; gap> IsBijectiveTransducer(T); false gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], [1]], > [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]);; gap> IsBijectiveTransducer(f); true gap> T := Transducer(2, 2, [[3, 2], [4, 4], [4, 4], [4, 4]], [[[], []], > [[0, 1], [1, 1]], [[0, 0], [1, 0]], [[0], [1]]]);; gap> IsBijectiveTransducer(T); true gap> T := Transducer(2, 2, [[1, 2], [3, 4], [1, 5], [1, 6], [3, 4], [1, 6]], > [[[0, 1, 0], []], [[1, 1], [0]], [[0, 1, 0], []], [[], [1, 0, 1, 0]], > [[1], [0]], [[], [1, 0]]]);; gap> IsBijectiveTransducer(T); false
‣ IsMinimalTransducer( T ) | ( attribute ) |
Returns: true or false.
A non-degenerate transducer T is called "minimal" it satisfies the following three properties: 1. Every state of T can be reached from the inital state of T. 2. If w is a word in the domain alphabet of T and s is a state of T, then the word written when w is read from state s is equal to the longest common prefix of the infinite words which can be wriiten (from the state s) by reading an infinite word with prefix w. 3. All the states of T define different maps from the space of infinite words in the domain alphabet of T to the space of infinite words in the image alphabet of T For a transducer T, the attribute IsMinimalTransducer(T) returns true if T is a minimal transducer, and false otherwise (with the following caveat). Caveat: Using standard definitions it is possible to have a minimal transducer which can write an infinite but eventually periodic word by reading a finite word. As the tranducers in this package don't allow this, we accomodate for these cases (breaking the second condition above) by having the transducer write the non-periodic part of the infinite words and then transitioning to a state which always transitions to itself and writes the periodic part of the infinite word when any letter is read. Each non-degenerate transducer has a unique minimal omega-equivalent form which can be computed with the operation "MinimalTransducer".
gap> T := Transducer(3, 3, [[3, 4, 3], [1, 3, 1], [1, 3, 3], [2, 2, 3]], > [[[2], [2], [0]], [[2, 0, 2, 1], [0, 0], []], [[], [2, 0], [1]], > [[], [2], [1, 1, 0, 1, 0]]]);; gap> IsMinimalTransducer(T); true gap> M := MinimalTransducer(T);; gap> IsMinimalTransducer(M); true gap> IsMinimalTransducer(CopyTransducerWithInitialState(M, 2)); true gap> T := Transducer(3, 3, [[3, 2, 1], [3, 3, 1], [2, 2, 1]], > [[[1, 0], [], [0]], [[], [], [0]], [[2], [2, 2, 1], [2, 2]]]);; gap> IsMinimalTransducer(T); false
‣ IsSynchronousTransducer( T ) | ( attribute ) |
Returns: true or false.
A transducer is called "Synchronous" if when it reads a finite word from any state, it always outputs a finite word of the same length. For a transducer T, the attribute IsSynchronousTransducer(T) returns true if T is a bijective transducer, and false otherwise.
gap> T := Transducer(3, 3, [[1, 2, 1], [3, 3, 3], [1, 3, 2]], > [[[1], [2], [1]], [[0], [1], [2]], [[0], [0], [1]]]);; gap> IsSynchronousTransducer(T); true gap> T := Transducer(3, 3, [[1, 2, 1], [3, 3, 3], [1, 3, 2]], > [[[1], [2], [1]], [[0], [1], [2, 1]], [[0], [0], [1]]]);; gap> IsSynchronousTransducer(T); false gap> T := Transducer(2, 2, [[1, 2], [4, 3], [1, 2], [2, 1]], > [[[1], [1]], [[1], [0]], [[0], [0]], [[1], [0]]]);; gap> IsSynchronousTransducer(T); true gap> T := Transducer(2, 2, [[1, 2], [4, 3], [1, 2], [2, 1]], > [[[], [1]], [[1], [0]], [[0], [1]], [[0], [0]]]);; gap> IsSynchronousTransducer(T); false
‣ IsomorphicInitialTransducers( T1, T2 ) | ( attribute ) |
Returns: true or false.
For transducers T1 and T2, with the same input and output alphabets, the operation IsomorphicInitialTransducers(T1, T2) returns true if and only if there is a bijection from the states of T1 to the states of T2 which preserves transitions, outputs and the initial state.
gap> T := Transducer(2, 3, [[1, 3], [2, 3], [3, 3]], [[[1], [2]], [[1], [2]], > [[0, 0], [1, 0]]]);; gap> T2 := CopyTransducerWithInitialState(T, 2);; gap> T3 := CopyTransducerWithInitialState(T, 3);; gap> T4 := CopyTransducerWithInitialState(T3, 3);; gap> T5 := Transducer(2, 2, [[1, 1], [2, 2], [3, 3]], > [[[], []], [[], []],[[], []]]);; gap> T6 := Transducer(3, 2, [[1, 1, 1], [2, 2, 2], [3, 3, 3]], > [[[], [], []], [[], [], []], [[], [], []]]);; gap> IsomorphicInitialTransducers(T, T2); true gap> IsomorphicInitialTransducers(T, T3); false gap> IsomorphicInitialTransducers(T, T4); true gap> IsomorphicInitialTransducers(T, T5); false gap> IsomorphicInitialTransducers(T, T6); false
‣ OmegaEquivalentTransducers( T1, T2 ) | ( attribute ) |
Returns: true or false.
For non-degenerate transducers T1 and T2, with the same input and output alphabets, the operation OmegaEquivalentTransducers(T1, T2) returns true if and only if T1 and T2 induce the the same continuous maps from the infinite words in their domain alphabets to the infinte words in their image alphabets. Alternatively one can write T1=T2 instead of OmegaEquivalentTransducers(T1, T2).
gap> T := Transducer(2, 2, [[2, 2], [3, 1], [3, 3], [5, 2], [2, 1]], > [[[1, 0], [0, 0]], [[1], []], [[0], [1]], [[1], [1]], [[], [0, 0]]]);; gap> M := MinimalTransducer(T);; gap> OmegaEquivalentTransducers(T, M); true gap> T = M; true gap> T := Transducer(2, 3, [[1, 3], [2, 3], [3, 3]], [[[1], [2]], [[1], [2]], > [[0, 0], [1, 0]]]);; gap> T2 := CopyTransducerWithInitialState(T, 2);; gap> T3 := CopyTransducerWithInitialState(T, 3);; gap> T4 := CopyTransducerWithInitialState(T3, 3);; gap> OmegaEquivalentTransducers(T, T2); true gap> OmegaEquivalentTransducers(T, T3); false gap> T = T4; true
‣ EqualTransducers( T1, T2 ) | ( attribute ) |
Returns: true or false.
For transducers T1 and T2, the operation EqualTransducers(T1, T2) returns true if and only if T1 and T2 have the same input alphabets, output alphabets, states, transition function and write function. Note that the operation "=" checks omega equivalence as opposed to running this operation.
gap> T := Transducer(2, 3, [[1, 3], [2, 3], [3, 3]], [[[1], [2]], [[1], [2]], > [[0, 0], [1, 0]]]);; gap> T2 := CopyTransducerWithInitialState(T, 2);; gap> T3 := CopyTransducerWithInitialState(T, 3);; gap> T4 := CopyTransducerWithInitialState(T3, 3);; gap> EqualTransducers(T, T2); true gap> EqualTransducers(T, T3); false gap> EqualTransducers(T, T4); false
‣ TransducerOrder( T ) | ( attribute ) |
Returns: A positive integer.
The input must be a transducer T with the same input and output alphabet, which induces a homomorphism on the set of infinite words over its alphabet. If this homeomorphism has finite order, then its order is returned.
gap> T := IdentityTransducer(5);; gap> TransducerOrder(T); 1 gap> T := Transducer(2, 2, [[1, 2], [1, 3], [1, 3]], [[[1, 0], []], [[0], > [1, 1]], [[0], [1]]]);; gap> TransducerOrder(T); 2 gap> T := Transducer(5, 5, [[1, 1, 1, 1, 1]], [[[1], [0], [3], [4], [2]]]);; gap> TransducerOrder(T); 6
generated by GAPDoc2HTML