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" :).