473,326 Members | 2,588 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Programming a Turing Machine

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
1 4268
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

147
by: Sateesh | last post by:
Hi, I am a beginner in Python, and am wondering what is it about the indentation in Python, without which python scripts do not work properly. Why can't the indentation not so strict so as to give...
32
by: Xah Lee | last post by:
is it possible to write python code without any indentation? Xah xah@xahlee.org http://xahlee.org/PageTwo_dir/more.html
0
by: Alex Vinokur | last post by:
C++ Simulator of a Nondeterministic Turing Machine has been added at : * http://alexvn.freeservers.com/s1/turing.html * http://sourceforge.net/projects/turing-machine/ Currently those sites...
0
by: Alex Vinokur | last post by:
C++ Simulator of a Universal Turing Machine can be downloaded at : * http://alexvn.freeservers.com/s1/utm.html * http://sourceforge.net/projects/turing-machine/ The program simulates a...
2
by: Ganesh | last post by:
I am not sure if the question is relevant to this group. Is there a proof that template metaprogramming is Turing-complete? Is the proof trivial - just replace all the template instantiaion with...
3
by: Kvele | last post by:
I'm just looking for Turing machine for divide two binary numbers by subtract. The input string of numbers can't be deleted. The result must contain arrear. I need list of states (or c source). For...
78
by: wkehowski | last post by:
The python code below generates a cartesian product subject to any logical combination of wildcard exclusions. For example, suppose I want to generate a cartesian product S^n, n>=3, of that...
43
by: Adem24 | last post by:
The World Joint Programming Language Standardization Committe (WJPLSC) hereby proclaims to the people of the world that a new programming language is needed for the benefit of the whole mankind in...
151
by: istillshine | last post by:
There are many languages around: C++, JAVA, PASCAL, and so on. I tried to learn C++ and JAVA, but ended up criticizing them. Is it because C was my first programming language? I like C...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.