I am looking to find an algorithm that would let me while starting at the right most of an input string containing blanks in between, merge input symbols so that there are no blanks.
For example, 0 _ 0 _ 0 _ into 000.
I am aware of methods shown in the form of state diagrams to merge input symbols when there are no blanks in between, but I would like to know of good a way to do it when this is not the case.
More example of what I mean by removing input symbols in between (assuming an alphabet of 1,0 for now):
- Example input: 10011 output: 101
- Example input: 11101101 output: 1110
I am not sure you can do that with only 2 alphabet symbols. Basic idea is to use additional (blank) symbol from alphabet and use it as skip characters when moving on tape.
If you know how to solve initial problem, for example 0_1_0 you can can covert arbitrary tape having only 0 and 1 to tape with blanks then proceed from there.