Create a Turning Machine: Pattern-deletion. Find every instance of a pattern and
ID: 3835714 • Letter: C
Question
Create a Turning Machine:
Pattern-deletion. Find every instance of a pattern and "delete" it. = { a, b }
The tape will have the following form:
<pattern-to-search-for>#<string-1>#<string-2># … <string-n>#
The pattern to search for will be non-empty, and should not be changed. There will
be at least one string to examine; each string will be non-empty. There may be
zero, one, or more matches. The group of strings begin and end with a pound sign;
each string is separated from the next one by a pound sign.
"Deletion" will be accomplished by writing x's over the matching string.
Do not reset the head. Restore all unchanged data (i.e., not x’d out).
Sample data (spaces for readability only – there are no spaces within the data;
underlining indicates the changes made):
input tape: ab # abba # bb # ab # babbb # pattern = ab
result tape: ab # abba # bb # xx # babbb # one instance found
input tape: a # bbb # aa # pattern = a
result tape: a # bbb # aa # no match, unchanged
input tape: baba # baba # aa # baba # ba pattern = baba
result tape: baba # xxxx # aa # xxxx # ba two matches
Explanation / Answer
To design this turing machine, follow these steps:
1. If we see 'a', then replace it with 'x' and move right till we have seen a # sign. Then go to step 2.
If we see 'b', then replace it with 'y' and move right till we have seen a # sign. Then go to step 3.
If we see '#' then go to step 5.
2. If we see 'a', then replace it with 'x' and move right till we have seen a # sign. Then repeat this step till Blank is seen.
If 'b' is seen, then move right till we see # sign. Then repeat step till blank is seen. go to step 4.
3. If we see 'b', then replace it with 'x' and move right till we have seen a # sign. Then repeat this step till Blank is seen.
If 'a' is seen, then move right till we see # sign. Then repeat step till blank is seen. go to step 4.
4. Move left till we see blank. Then move right till we see either #, or a or b. Move left one symbol and go to step 1.
5. The strings have been processed already. So we need to replace the x with a and y with b in the pattern.
Move left till blank is seen while replacing x with a and y with b.