The input to a Turing Machine (TM) is always a string. The tape contents are populated with this string. The TM runs a computation on this input string.

Consider the following problem. Given a DFA and a string does accept ? In other words, devise a TM to check wether is accepted by a DFA .

Here the input to a TM is and .

What is ?

The DFA can be defined as a 5-tuple . Each element in this set can be represented as a string. The combined string representation of this DFA is denoted as . Thus is a DFA while is its string representation.

The above DFA can have the following string encoding. Notice the separators to keep track of each component. This representation contains all the information about the DFA – the states, the transitions etc.

is already a string. Concatenating, the input to the TM is . This means that the input tape is populated with the string representation of the DFA and the string that has to be checked for acceptance.

The TM can simulate the computation of the DFA on by reading the string representation and keeping track of the start state, transitions, final state etc.