November 2nd, 2011, 06:59 AM  #1 
Newbie Joined: Nov 2011 Posts: 3 Thanks: 0  Turing machine
{w  w does not contain twice as many 0s as 1s over the alphabet {0, 1}}. Draw state diagram and give formal description. 
December 28th, 2011, 11:08 AM  #2 
Newbie Joined: Dec 2011 From: Sao Paulo, Brazil Posts: 15 Thanks: 0  Re: Turing machine
I dont have right a graphic software to draw the diagram, but I can give you the formal description: " Input: A string w 1. For each 1 on the tape, do 2. mark this 1 and scroll over the tape until you find two 0 simbols (not necessarily in sequence), and mark then. If you don't find this two zero, accept. 3. Scroll over the tape and if you find just marked 1s and marked 0s , reject. Else, accept." Line 2 will stop the machine if w has more 1s than two times 2s, and line 3 will reject if w has exacly twice has many zeros as 1, and accept otherwise (in case you have more 0s than 1s, but not twice as many, wich will leads to the case that the machine will contained a non maked zero). I hope I could help, and let me know if you find any mistake above. 

Tags 
machine, turing 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Turing Machine  krausebj0  Number Theory  1  June 28th, 2013 04:01 AM 
Turing machine 2  jenifer  Applied Math  0  November 2nd, 2011 07:50 AM 
Turing Machine Problem... Help please  ikurwa  Applied Math  0  April 16th, 2011 10:37 PM 
Help On Turing Machine Problems Please  Christi123  Applied Math  1  April 14th, 2008 04:33 AM 
A Turing Machine Question  Christi123  Applied Math  0  March 22nd, 2008 03:25 PM 