By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,967 Members | 1,690 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,967 IT Pros & Developers. It's quick & easy.

Programming a Turing Machine

P: n/a
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.

Dec 15 '06 #1
Share this Question
Share on Google+
1 Reply


P: n/a
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" :).

Dec 15 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.