Motivated by the study of various kinds of machines as recognizers of formal languages, the
authors compare the encoding and decoding power of finite state sequential machines and
extensions thereof. They show that, with a forward moving head, the best compression
achievable for a given sequence, to be decoded by a finite state decoder, is the same as the
best ratio attainable for that sequence when encoded by a finite state information lossless
encoder. They cannot gain in compression by allowing a finite state encoder to move its …