benachi@loria.crin.fr (Benachi Saad) (03/19/91)
I would appreciate any comments thoughts, references to works related to the following subject : Suppose we have a finite input-output automaton M = (Q, A, d, s, q0, F) where M' = (Q, A, d, q0, F) is a classical finite automaton and s is an output function. The behaviour of M for an input word u is defined by the following algorithm : Let p be the current state and a the current letter ; (1) If there is a state r such that d(p, a) = r Then go to the state r; Else /* there is no transition from p labelled with a */ write a on the output tape Fi read the next letter ; repeat (1) until the read-head reaches the right end of the input word u ; We have as a result a state q and an output word v. We call such a process a pass of M on u starting in state p and write : g(p, u) = (q, v). We say that M goes in an new pass if M starts with as current state q and input word v and write g^2(p, u) = g(g(q, v)). It is easy to see that after a number n of passes we have : g^n(p, u) = (q, empty_word) or g^n(p, u) = (q, v) and g(q, v) = (q, v) Define the language L(M, n) accepted by M in a finite number n of passes to be the set of words : { u such that there exist an integer l <= n ; g^l(q0, u) = (qf, empty word) and qf is in F } Conjecture : L(M, n) is recognizable ???? Thanks in advance.