0

I got recently introduced to automata and couldn't find an answer to the following question: Let $A$ and $B$ two finite state automata (with a starting state) acting on the same formal language $\Omega$.

Can we describe the map $A \circ B: \omega \mapsto A(B(\omega))$ also as a finite state automaton?

If not, does it work for $A=B$, i.e. are iterations of the same finite state automaton again finite state automatons?

ctst
  • 1,424
  • Finite automatons have a single output: either "accept" or "not accept" (or, equivalently, 1/0, yes/no, etc). Since the domains of both $A$ and $B$ are strings and ranges are {"accept", "not accept"}, the output of one cannot be plugged into the other. – John_Krampf Jul 16 '22 at 22:27
  • It is possible to chain transducers together, if the output alphabet of the first transducer is included in the input alphabet for the second transducer. Transducers are an extension of automatons that emit a (possibly null) character for each character in the input. – John_Krampf Jul 16 '22 at 22:29
  • Ok, maybe I got taught the wrong word and mean transducers. To clarify: For me an automaton takes an infinte ray of 0 and 1 and each state converts the next letter and jumps to the next corresponding state (depending on the input letter). So it converts rays to rays. The question I have now, if the concatenation of two finite state transducers (?) as functions on $\Omega$ are again finite state. – ctst Jul 16 '22 at 22:36
  • 1
    Yes. Assuming they have the same input and output alphabets (you say the alphabet is {0, 1} so this is true) then the concatenation of two finite state transducers is again a finite state transducer. To see this, first note obviously the end result is a transducer, you're just checking if it's a finite state transducer. And yes it is since an FST is characterized by having a finite number of states, and you can bound the number of states of the concatenated FST by the product of numbers of states of the two FSTs you're concatenating. – John_Krampf Jul 16 '22 at 22:41
  • Ok, I think i got it from here, thanks. The states are (a_i,b_j) and they act via (a_i,b_j)(x) -> (a_i(b_j)(x), b_j(x)) (as resulting states after a letter x and the output accordingly as a_i(b_j(x))). Well that was simple enough to not put it anywhere :-) – ctst Jul 16 '22 at 22:44
  • yep you got it :) – John_Krampf Jul 16 '22 at 23:45

0 Answers0