Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Programming a Turing Machine

Reply
Thread Tools

Programming a Turing Machine

 
 
roxorsoxor2345
Guest
Posts: n/a
 
      12-15-2006
I am very sorry if this is not the appropriate group to post this
question.

I currently have a program that tests strings to see if they are
palindromes. My input file looks something like this:


0 a # R 1 (# is representation for a blank)
0 b b R 1
0 # # L 2
1 a a R 2
..
..
..etc... (followed by a list of strings i wish to test)


This is a transition table that works like this:
column 1 is the current state
column 2 is the currenty symbol on the tape (the tape contains my
string to test)
column 3 is what the new symbol should be
column 4 tells the head of the tape to move left, right, or stay still.

column 5 tells me what the new state is.


Like I said, I have a program that works for palindromes, however I
need to modify it to accept strings of the type (a^n)(b^2n)(c^n)


All I need is a new transition table, and new strings to test, and I'm
set. However I am having a tough time coming up with a working
transition table for this problem. I know that if I could draw the
picture I could come up with the transition table, but I can not get my

turing machine quite right. Any help would be appreciated.

 
Reply With Quote
 
 
 
 
frame
Guest
Posts: n/a
 
      12-15-2006
roxorsoxor2345 wrote:
> I am very sorry if this is not the appropriate group to post this
> question.
>
> I currently have a program that tests strings to see if they are
> palindromes. My input file looks something like this:
>
>
> 0 a # R 1 (# is representation for a blank)
> 0 b b R 1
> 0 # # L 2
> 1 a a R 2
> .
> .
> .etc... (followed by a list of strings i wish to test)
>
>
> This is a transition table that works like this:
> column 1 is the current state
> column 2 is the currenty symbol on the tape (the tape contains my
> string to test)
> column 3 is what the new symbol should be
> column 4 tells the head of the tape to move left, right, or stay still.
>
> column 5 tells me what the new state is.
>
>
> Like I said, I have a program that works for palindromes, however I
> need to modify it to accept strings of the type (a^n)(b^2n)(c^n)
>
>
> All I need is a new transition table, and new strings to test, and I'm
> set. However I am having a tough time coming up with a working
> transition table for this problem. I know that if I could draw the
> picture I could come up with the transition table, but I can not get my
>
> turing machine quite right. Any help would be appreciated.


I don't know whether this might be of help to you, but I thought of the
following "Context-sensitive grammar" for the language
(a^n)(b^2n)(c^n):

S -> MSN | e
MN -> abbc
Ma -> aM
Mb -> abb
cN -> Nc
bN -> bbc

Example: - Derivation of (a^2)(b^4)(c^2)

S => MSN (using S -> MSN)
=> MMSNN (using S -> MSN)
=> MMNN (using S -> e)
=> MabbcN (using MN -> abbc)
=> aMbbcN (using Ma -> aM)
=> aabbbcN (using Mb -> abb)
=> aabbbNc (using cN -> Nc)
=> aabbbbcc (using bN -> bbc)

As it's possible to construct a "linear bounded automaton" for this, a
"Turing Machine" should also be possible.

Clue: -
====

You said that you have a program that works for palindromes, whose
Context-free grammar should have been as follows: -

S -> aSa | bSb | cSc | a | b | c | e

Now figure out how the transition table is implementing the above
grammar, then adopt the table to work for the grammar devised for
(a^n)(b^2n)(c^n). You can do it!

P.S.: - I am sorry if you don't find my above suggestion useful; I am a
C++ programmer and am bit old to "Theory of Computation" .

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SUMMARY] The Turing Machine (#162) Matthew Moss Ruby 4 05-16-2008 07:15 PM
[QUIZ] The Turing Machine (#162) Matthew Moss Ruby 26 05-13-2008 05:03 PM
Turing machine Kvele C Programming 3 01-07-2005 03:23 AM
C++ Simulator of a Universal Turing Machine Alex Vinokur C++ 0 12-19-2003 05:24 AM
C++ Simulator of a Nondeterministic Turing Machine Alex Vinokur C++ 0 11-12-2003 06:47 PM



Advertisments