- #1
cereal01
- 1
- 0
Homework Statement
I need to construct and describe work od Touring machine which will calculate the value of logical expression with Boolean operators AND and OR. The simbol of input track which match logic operator AND is *, and simbol od input track that match logic operator OR is +.
Touring machine must first check is the input line correct and then calculate the result of logical expression which is given.
Sample of input line is 1+1*0+1*1
Homework Equations
I think that i need to construct it with tables and states, so any kind of help will be great.
The Attempt at a Solution
Symbols: 0 1 + *
OR AND blank
Suggest: operate bitwise on least significant bit of operands first and work towards the most significant bit.
+ 0 1 * 0 1
0 0 1 0 0 0
1 1 1 1 0 1
Precedence: * operates before +
This suggests the initial state should search for a ' * ' or the end-of-tape, which may require
its own symbol since the tape can be infinite.
Hmm, two possibilities... that suggests a binary tree.
If there are no ' * ' symbols left and we reach the other end of the tape (but having two ends may also be a problem) then the expression has no '*'s and we'd have to move on to looking for '+'s.
Since there should be an operator precedence, e.g. operating * before +, the initial state should search for a * (just like we do with a math problem).
The Turing machine (TM) should reach a * or find the end-of-data (and that has to be worked out too). If it finds a *, then it will look for 0s and 1s:
It will record what it sees by changing state according which bit it has just read. At the same time, it is looking for the end of the operand.
When it reaches the end of the operand, it will transition to another state (depending on whether the last bit was 0 or 1).
It will have to erase that operand bit, and then go in the reverse direction to find the corresponding operand bit on the other side of the *.
When it reaches that bit, it will have to erase the bit and change state (again according to the bit value), and then ('knowing' the answer) it will have to move to the answer area.
(If there is some special symbol to separate the answer field from the expression area, it might be easier to write out the answer bits in reversed order (and reverse them again later).
It might be easier if the special symbol were a new symbol (like '=').
After an answer bit has been written, the TM will have to go back to the expression to work on the next more significant bits of the operands.
If, after the TM has calculated an answer bit, it passes over more operators, it will have to count the operators--it will have to change state for each instance of the current operator symbol (either * or +) being considered. There should be a limit to the number of each kind of operator that may appear, perhaps a maximum of two of each as in your example.
After the * operations are completed, and the * symbols have been appropriately erased, there will be no more * symbols, and the TM will enter another group of states where it will handle only the + symbols.
Somehow it will have to re-write the product into the expression, or maybe reconstruct the simplified expression (sum of products, or OR of ANDs) in the answer field.
If, while it reconstructs the expression in simplified form, it erases the original expression field, then it will have a new, simpler expression on the other side of the special symbol. Now the directions are reversed where the expression to be evaluated is and where the answer field to be completed is located. Of course, now the TM only has to handle the + symbol. The TM would handle the + in a similar way, or maybe it can do all (if more than two) operands simply: if it ever sees a 1 bit, the answer bit will be a 1; otherwise it will be a 0.
Again it will have to move towards the special symbol separating the expression field and the answer field and cross it to get to the answer field and write the answer bit.
So, for your 1+1*0+1*1 example, maybe something like:
Start in state 0, move right, read symbol
symbol is a:
0, go to state 2
1, go to state 3
Now in state 3, continue moving right
Possible symbols to see: 0, 1, *, +, blank, special symbol
See:
0, go to state 2
1, go to state 3
if in state 0 and TM sees a *, go into state 4: have to go back one space, erase the bit, and continue onward.
if in state 1 and TM sees a *, go into state 5: have to go back one space, erase the bit, and continue onward.
if in state 0 and TM sees a + ...
if in state 1 and TM sees a + ...
if in state 0 and TM sees a blank ...
if in state 0 and TM sees a special symbol ... (this should not happen at this point because only one operand was found,and it should not happen ever if the bit strings are required to all have the same number of bits.)
Now the state holds the information on the first bit value and the * operation. Look for the second operand's bit.
I haven't done this, but maybe it would be helpful to draw up a tree diagram to account for the possibilities in each stage. It seems each position in the tree would probably represent a separate state. So, maybe a tree for the first pass (to operate on two bits), a second tree for the second pass, and so forth. Then it might be possible to re-use some of the same sets of states (or trees), letting the 'answer' bits and the remaining portion of the input expression control how the TM switches between the trees or to a new group of trees (states).