15 replies to this topic

[dole]

hi

i got the assignment to do a program that builds grammar L(G) = L(M) for assigned turing machine.
well i am well over my head, and i dont even know where to begin. i know little bout turing machine theory and could possibly implement some easier turing, but this...

so i am asking for any kind of help (i am somewhat hoping to find a good soul who could do this for me, but any kind of help is welcome).

[bobdark]

let me get it right - the input to your program is a turing machine?
What can you assume about this turing machine? Does it halt for every input? How do you interpret the input? I mean, how do you decode the input to get the machine?
Anything you can assume on its language?

[dole]

well i find the assignment formulated little weird. that is one of the problems why it is kinda hard.
full text of the assignment goes like this:
implement on computer program that will for assigned turing machine build corresponding grammar (L(G) = L(M))

[dargueta]

This is really vague. Do they want a full-out C/C++ implementation, or just pseudocode?

[dole]

dargueta said:

This is really vague. Do they want a full-out C/C++ implementation, or just pseudocode?

they want full implementation (doesnt need to be C/C++, but it is the language i know most, so C :) ).

i got information from a friend that i should implement it something like this:
Turing Machine To Unrestricted Grammar

so i think it will need to accept any turing(probably transitions in an input file) and convert it to unrestricted grammar. at least now i know what to do :)

btw if someone has seen or has source of smth like this pls post it here.

[dargueta]

Start by defining an input format for your Turing machine description. It shouldn't be more than two or three sentences, by my count.

[dole]

well i have previously made a turing machine that multiplies 2 numbers, so i will use struct from there (cause it already has a parser) or smth similar to it, so it will accept turing transitions smth like this:

(q0, a)=>(q1, b, R)

q0->current state

a->input sign

q1->new state

b->replacing the input sign

R->shift to the right

now i found what i think is the correct alghorithm on the net
http://www.cs.usfca....1/lecture13.pdf
from 13-49 i think it reffers to my assignment. from what i see i need to do turing simulator in reverse.

well i g2g now, so i will post few questions later...

[dole]

argh... the more i read the more i become confused... dont know right from wrong now... sometimes too much material harms you..

can someone explain to me in plain words how will i from transitions in above link get grammar. here is example
(q0,a),(q1,->) transition gets you
aaQ1->aQ0a
abQ1->aQ0b
auQ1->aQ0u

and what does -> in transition mean? shift to the right? or arrow in grammar production?

[dargueta]

Your transitions are incomplete. Turing machine transitions are quintuples, namely:

(current state, symbol under read head) --> (Next state, symbol to write, direction to move head).

[dole]

yeah i know that, but in the link they are like that. probably cause state represents nonterminal sign, so it should be (q0,a),(q1,q1,->), so it probably doesnt matter, if you write it that way...

[dargueta]

I dunno. Not the way I learned it, but there's a lot of ways to kill a cow.

[dole]

yeah i know.. .well i am thinking of a new solution.. cant get it in my head cause i didnt see any source that has turing and grammar in it. all i have are tons of pages of theoretical alghorithms, but not one implementation (and i hate theory).