Question: L = { ww:win Sigma ^ ( + ) } Construct a Standard Turing Machine M such that L ( M ) = L
Lww:winSigma
Construct a Standard Turing Machine M such that
LML
Save your Standard Turing Machine as a JFLAP file, and
submit that file to Canvas as your solution to this exercise.
suppose that wab Then, wwabab. In this case, the tapes contents could go through the following evolution, toptobottom reflecting the tapes contents as time progresses
ababTapes initial contentsxbabAfter changing leftmost a to xxbayAfter changing rightmost b to yxyayAfter changing leftmost b to yxyxyAfter changing rightmost a to x At this point in processing, the readwrite head can be positioned over the leftmost symbol in the second half of the string. All symbols from there to the right could be changed back to a s and b s after which, the tape's contents would look like this
mathrmxmathrmvmathrmamathrmbmid leftarrow After restorina a s and b s in second half of strina
Next, one could match each x in the left half of the string to an a in the second half, and match each y in the left half with a b in the second half. The tape's contents would go through the following evolution
If all such matching succeeds, the original input string can be accepted. If there arises a situation in which such matching cannot be done, the original input string can be rejected.
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
