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"

.