November 24th, 2013, 03:44 PM
1) How would you create a Turing machine that accepts words w formed with the a, b, c letters so that #a(w) + #b(w) != #c(w), where #a(w) means the number of "a" 's from the word w etc.
Could we use a Turing machine with two tapes to separate on the first tape all the letters of a and b, on the 2nd all the c letters and then to compare the lengths? Is there an easier method?
2) Turing machine that returns the value of f(n)=2^n-1, if we give it the input n.
I could use a Turing machine to compute 2^n in this way:
on the first tape I have the representation of n ( 111111...11 - n+1 times), on the second tape I have 111 = representation of 2, and then on an additional tape, for every 1 in the representation of n, I copy the previous tape, for 2 times. And I generate the number 4. then I copy on another tape the previous tape, 2 times, and I get 2^3 etc. of course, I have to pay attention to the additional 1 from every tape. ( to delete it and then add it again...)
And then I delete a '1' from the last tape, to get 2^n-1.
Is it ok, is there an easier method?
November 24th, 2013, 09:42 PM
What you mean by "accept" by the way?
If it is about switching to the state qY if the word was acceptable and qN if was not, I think the following approach could be used:
- seek for letter 'a', when found change it to 'x' and rewind to start of the word;
- seek for letter 'b' to change it to 'x' too - if not found, switch to qN;
- seek for letter 'c' to change it to 'x' too - if not found, switch to qN;
- when no more 'a's found, seek for any 'b' or 'c' - if anything found, switch to qN - otherwise switch to qY.
Word should be bordered by spaces, for example, so that machine could recognize the ends.
It sounds you are trying to make matters more complicated than necessary. Store the values in binary system.
Let the first tape to store the N, for example '11001', and the second tape at beginning should have only '0'.
You need to write the procedure of decrement-by-one for the first tape:
- seeking from the end, find first '1' and change it to '0';
- then change all chars from this point to end to '1'.
Now simply improve this procedure - let it add another '1' at the end of the number on the second tape - so you'll have successive values of '2^k-1'. (i.e. 01, 011, 0111, 01111 etc.)
Stop when the value on the first tape have no more '1's
November 27th, 2013, 06:51 AM