Explore BrainMass
Share

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

then

w^R = bba
ww^R = abbbba

© BrainMass Inc. brainmass.com March 21, 2019, 1:49 pm ad1c9bdddf
https://brainmass.com/computer-science/theoretical-computer-science/turing-machine-even-palindromes-106757

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

$2.19