GAP (aaa) - Chapter 4: Words accepted by transducers and word operations

In this chapter we decribe the words that are accepted by an aaa transducer, as well as operations that can be performed to them.

4.1 Words and operations

4.1-1 IsPrefix

A word p is a prefix of the word w if w = pq for some word q. The operation IsPrefix(u, v) returns true if the word v is a prefix of the word u, and false otherwise.

gap> u := [0, 1];; v := [0, 1, 0];; empty := [];;
gap> IsPrefix(u, v); IsPrefix(v, u); IsPrefix(u, empty);
false
true
true

4.1-2 Minus

If v is a prefix of u, then u = vm for some word m, and the operation Minus(u, v) returns m. Otherwise, it returns fail.

gap> u := [0, 1];; v := [0, 1, 1];;
gap> Minus(v, u);
[ 1 ]
gap> Minus(u, v);
fail

4.1-3 GreatestCommonPrefix

If list is a list of words, the operation GreatestCommonPrefix(list) returns the greatest common prefix of all the words in list.

gap> u := [0, 0];; v := [0, 0, 1, 2];; w := [0, 1, 2];;
gap> GreatestCommonPrefix([u, v, w]);
[ 0 ]
gap> empty := [];; z := [1];;
gap> GreatestCommonPrefix([u, v, w, empty]);
[  ]
gap> GreatestCommonPrefix([u, v, w, z]);
[  ]

4.1-4 PreimageConePrefixes

If u is a word with letters from the output alphabet of the transducer T, and s is a positive integer, the operation PreimageConePrefixes(u, s, T) returns the list P of prefixes such that if w = pq for some p in P, and some other word q, then the image of w when read by T from state s is uv for some word v. This operation is meant to emulate the inverses of the functions f_q discussed in the last two paragraphs of p.142 in [GNS00].

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> PreimageConePrefixes([0], 2, f);
[ [ 0 ], [ 1, 0 ], [ 1, 2 ] ]
gap> TransducerFunction(f, [0], 2); TransducerFunction(f, [1, 0], 2);
[ [ 0, 0 ], 1 ]
[ [ 0, 2 ], 1 ]
gap> TransducerFunction(f, [1, 2], 2);
[ [ 0, 1 ], 2 ]

4.1-5 ImageConeLongestPrefix

If u is a word with letters from the input alphabet of the transducer T, and s is a positive integer, the operation ImageConeLongestPrefix(u, s, T) returns the greatest common prefix of the set { L(uv, s) | v is word with letters in I} where L and I abstractly represent the output function and input alphabet of T, respectively.

gap> t := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], []],
>                           [[1, 0, 0], [1], [1]], [[0, 2], [2], [0]]]);;
gap> ImageConeLongestPrefix([], 2, t);
[ 1 ]

4.1-6 TransducerImageAutomaton

For a transducer T, the operation TransducerImageAutomaton(T) returns an automaton object (https://www.gap-system.org/Manuals/pkg/automata/doc/chap2.html#X821C3B3687B1F2FF) which accepts the language of finite words which are prefixes of the words which can be written from the initial state of T.

gap> T := Transducer(3, 3, [[3, 2, 3], [1, 3, 1], [1, 3, 1]],
> [[[1, 1], [0], [2]], [[1], [1], []], [[2, 0], [0, 1, 0], []]]);;
gap> String(TransducerImageAutomaton(T));
"Automaton(\"epsilon\",7,\"012@\",[ [ [ 2 ], [ ], [ 6 ], [ ], [ 1 ], [ ], [ 3 \
] ], [ [ 4 ], [ 1, 3 ], [ ], [ 3 ], [ ], [ 7 ], [ ] ], [ [ 3 ], [ ], [ 5 ], [ \
], [ ], [ ], [ ] ], [ [ ], [ 1 ], [ 1 ], [ ], [ ], [ ], [ ] ] ],[ 1 ],[ 1 .. 7\
 ]);;"
gap> T := Transducer(2, 2, [[2, 3], [5, 1], [4, 5], [2, 5], [3, 3]],
> [[[0], [0]], [[0, 1, 0, 0, 0, 1], [0, 0, 0]], [[], [0]],
> [[], []], [[0], [0]]]);;
gap> String(TransducerImageAutomaton(T));
"Automaton(\"epsilon\",12,\"01@\",[ [ [ 2, 3 ], [ 6, 11 ], [ 5 ], [ ], [ 3 ], \
[ ], [ 8 ], [ 9 ], [ 10 ], [ ], [ 12 ], [ 1 ] ], [ [ ], [ ], [ ], [ ], [ ], [ \
7 ], [ ], [ ], [ ], [ 5 ], [ ], [ ] ], [ [ ], [ ], [ 4 ], [ 2, 5 ], [ ], [ ], \
[ ], [ ], [ ], [ ], [ ], [ ] ] ],[ 1 ],[ 1 .. 12 ]);;"
gap> T := Transducer(3, 4, [[1, 1, 2], [1, 1, 3], [1, 1, 1]],
> [[[0], [1], []], [[2], [3,0], [3]], [[1], [2], [3]]]);;
gap> String(TransducerImageAutomaton(T));
"Automaton(\"epsilon\",4,\"0123@\",[ [ [ 1 ], [ ], [ ], [ 1 ] ], [ [ 1 ], [ ],\
 [ 1 ], [ ] ], [ [ ], [ 1 ], [ 1 ], [ ] ], [ [ ], [ 3, 4 ], [ 1 ], [ ] ], [ [ \
2 ], [ ], [ ], [ ] ] ],[ 1 ],[ 1 .. 4 ]);;"

The following images correspond to the first of the transducers in the above example and can be generated with the commands "Splash(DotTransducer(T))" and "DrawAutomaton(TransducerImageAutomaton(T))" respectively.