Automata theory was conceived by Alan Turing, who was widely accepted as the father of modern computer science. Interestingly, most of Turing’s earlier work evolved around breaking the code encrypted by the Nazi Enigma machine. In short, the Enigma machine is an encryption machine. It takes a string of input symbols, and transform the symbols into a different output stream. A machine to break the encryption needs to take the encrypted input stream of symbols, and determine its original content.
The mechanism of the Enigma machine was discovered fairly early. However, the mechanism itself did not lend a hand in the deciphering of encrypted messages. This is because the setting of the rotors of the Enigma machine can create 1023 encryption combinations. Each input symbol to the Enigma machine changes the encryption map for the next symbol!
With the invention of the Colossus, it is possible to try many encryption combinations. This is great, but how do we know that a particular encryption combination works? A code is broken when the transformed message contains common letters or known plain text sequences that are present in every message.
Knowing a little bit of this background, we can now proceed to discuss automata theory!