Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an academic exposition of applications of finite state machines (like, e.g., Mealy machines) in cryptography and ciphers? There is a mention about things like that in Wikipedia article on Mealy machines (subsection “Applications”). So the links to some academic texts play up on this are very appreciated. Alternatively would you share your thoughts on how to furnish this topic (FSM in cryptography) for students?

  • $\begingroup$ I can't understand what you are asking. There are a bunch of sentences but nothing that ends with a question mark. What is your question, exactly? Please edit the question to be more specific and clearer about exactly what you are asking. Help us to help you. Generally this site is not a perfect fit for "can you suggest references in the following field" or "can you suggest more references that are sorta like the following ones", particularly if it is an open-ended request. See meta.cs.stackexchange.com/q/303/755 $\endgroup$ – D.W. Aug 17 '13 at 23:53

Consider the coding $a \to 0$, $b \to 1010$, $c \to 100$, $d \to 1011$, $r \to 11$.$\ \ $ I let you guess what represents $010101101000101101010110$ in this coding, but this can be easily computed by a sequential machine, as illustrated here, slides 9-10.

What is the theory behind this? A subset $P$ of $A^+$ is a prefix code if no element of $P$ is a proper prefix of another element in $P$. For instance, the sets $\{0, 1010, 100, 1011, 11\}$, $0^*1$ and $\{0^n1^n \mid n > 0\}$ are prefix codes, with $A = \{0, 1\}$. Prefix codes are conveniently represented by the leaves of a tree. In particular, variable-length Huffman codes, the UTF-8 code and the Morse code are of this type.

Now if $B$ is another alphabet and $f:B \to P$ is an injective function, then $f$ extends uniquely to an injective monod morphism (coding) from $B^*$ to $A^*$. Further, if $P$ is a finite subset of $A^+$, the decoding function $f^{-1}$ can be computed by a sequential machine. This machine is essentially the minimal automaton of $P^*$, equipped with appropriate outputs (see the example).

Variable-length codes (whose prefix codes are a special case of) form the topic a rather advanced theory. The main reference is:
J. Berstel, D. Perrin, C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge: Cambridge University Press (2010). ISBN 978-0-521-88831-8.


Not the answer you're looking for? Browse other questions tagged or ask your own question.