My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
November 2nd, 2011, 07:59 AM   #1
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.
jenifer is offline  
December 28th, 2011, 12:08 PM   #2
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.
tsouzab is offline  

  My Math Forum > College Math Forum > Applied Math

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 05:01 AM
Turing machine 2 jenifer Applied Math 0 November 2nd, 2011 08:50 AM
Turing Machine Problem... Help please ikurwa Applied Math 0 April 16th, 2011 11:37 PM
Help On Turing Machine Problems Please Christi123 Applied Math 1 April 14th, 2008 05:33 AM
A Turing Machine Question Christi123 Applied Math 0 March 22nd, 2008 04:25 PM

Copyright © 2019 My Math Forum. All rights reserved.