Explore BrainMass

Explore BrainMass

    Turing Machine for even palindromes

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

    Construct a turing machine that accepts the language {ww^R : w <- {a,b}+}, where w^R denotes w superscripted R - reverse of w. For example, if

    w = abb


    w^R = bba
    ww^R = abbbba

    © BrainMass Inc. brainmass.com June 3, 2020, 7:39 pm ad1c9bdddf


    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 marker symbol.

    * You can construct ...

    Solution Summary

    Solution gives a transition list for the given turing machine, using which you can easily construct a graphical representation of it.