Explore BrainMass
Share

Explore BrainMass

    Turing Machine: Sequences with equal number of 1s and 0s

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Give the transition list for a turing machine that will determine whether for an input sequence w over symbol set {0,1}, n0(w) = n1(w).

    n0(w) and n1(w) respectively indicate the count of 0s and 1s in the word 'w'.

    © BrainMass Inc. brainmass.com May 20, 2020, 2:54 pm ad1c9bdddf
    https://brainmass.com/computer-science/theoretical-computer-science/turing-machine-sequences-equal-number-106758

    Attachments

    Solution Preview

    Notations used for denoting a turing machine transition are as follows.

    (StartState, SymbolRead) --> (EndState, SymbolWritten, MovementDirection)

    * Movement Directions are denoted by R (right) and L (left).
    * E is used to denote NULL symbol (or absense of symbol in a tape cell).
    * $ denotes a ...

    Solution Summary

    Given turing machine also accepts empty word, because in that case "n0(w) = n1(w) = 0".

    Apart from the list of transitions for the turing machine, solution also provides stepwise guidance on how to construct a graphical representation for the same.

    $2.19

    ADVERTISEMENT