4 DFAs

A DFA (deterministic finite state automata) is also called a DFSM (deterministic finite state machine). From the mathematical point of view, it can be described as a five-tuple M = (S,Σ,T,s,A), in which:

• S is a finite set of “states”. In the case of a DFA, a “machine” can be in one state at any particular moment. The set S enumerates all the possible states that a machine can be in. If you think about encryption (using the Enigma machine), a “state” corresponds to a particular configuration of the rotors and connectors of the encryption device. Note that a code breaking machine is an emulator of an Enigma machine, and hence it, too, must maintain the same states.
• Σ is a finite set of “symbols”. A single symbol (an element of Σ is an individual (atomic) external stimulus that can be presented to a machine. In the case of the Enigma machine, in the encryption process, a key press on the keyboard represents a symbol. Note that symbols can also be used for output purposes. In the case of the Enigma machine, the symbols on the machine that light up are also in the set Σ. This set of symbols also become the set of input symbols to a code breaking machine.
• T is a function such that T ⊆ S × Σ × S, or we can say that T : (S × Sigma) → S. Presented with a tuple (s,σ), T permits us to find the next state s′. In other words, T(s,σ) = s′, in which s is the start state, σ is the input symbol, and s′ is the end state.
  • In the case of the Engima machine, s represents a particular configuration of the rotors and connectors, σ represents the pressing of a particular key, and s′ represents the new configuration of rotors and connectors. To a code breaking machine, this function allows it to emulate the behavior of an Engima machine.
  • In some contexts, T : (S × Σ) → (S × Σ). In this case, the transition function not only specifies the next state of a machine (based on the previous state and an input symbol), but it also specifies what symbol the machine should output. This makes sense in the case of a code breaking machine, as the output symbol is the deciphered symbol based on the input (encrypted) symbol.
• s is the start state, it must be an element of S. In the case of the Enigma machine, s represents the initial positions of the rotors and connectors.
• A is a set of accept states, and A ⊆ S. An “accept state” is also called a “final state”. If a machine transitions into a final state, then the machine can “halt” to indicate that the input symbol sequence is accepted. In the case of the code breaking machine, a final state represents the recognition of a known sequence of symbols (called a crib) in the decoded message.

From M, we can discuss a language set L ⊆ Σ^∗. Σ∗ is called the “Kleene closure” of Σ. All it means is that Σ^∗ = {ε}∪ Σ ∪ Σ × Σ ∪ Σ × Σ × Σ ∪…. The symbol ε means the empty string. As a result, Σ^∗ represents the set of all strings that consist of symbols in Σ.

The special property of L is that every element in L is a string of symbols that leads to an “accept” state of a particular machine M. L is called the “language” of M. In the case of a code breaking machine, L is the set of all encrypted known text sequence in a message.