String Encoding of Machines – What is <M>?

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 M and a string w does M accept w? In other words, devise a TM to check wether w is accepted by a DFA M.

Here the input to a TM is w and M.

What is <M>?

The DFA M can be defined as a 5-tuple (Q, \Sigma, \delta, q_0, F). Each element in this set can be represented as a string. The combined string representation of this DFA is denoted as <M>. Thus M is a DFA while <M> is its string representation.

Rendered by

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.

Rendered by

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

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

5 Comments String Encoding of Machines – What is <M>?

  1. Pingback: Decidable Languages : ADFA, ANFA, AREX, ARG - TheBeardSage

  2. Pingback: Decidable Languages : EDFA, ENFA, EREX, ERG - TheBeardSage

  3. Pingback: Decidable Language : EQDFA - TheBeardSage

  4. Pingback: Decidable Languages : ACFG, APDA - TheBeardSage

  5. Pingback: Decidable Languages : ECFG, EPDA - TheBeardSage

Leave a Reply

Your email address will not be published. Required fields are marked *