Re: Question about Programming a Turing Machine
- From: "frame" <v.srikar@xxxxxxxxx>
- Date: 16 Dec 2006 00:12:35 -0800
Chris Smith wrote:
frame <v.srikar@xxxxxxxxx> wrote:
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):
The construction of a Turing machine from a context-free grammar is
possible, but far more difficult than just building the machine
intuitively from the original problem description. I doubt this would
be the correct way for rhaazy to proceed. Rick Decker's response gives
an easy approach to the problem.
Take a close look at my grammar (especially at the example derivation),
it indirectly suggests a way to construct the Turing Machine(TM).
Incidentally,
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!
Consider, construction of a TM for palindromes over the alphabet {a,b}
It's CFG, S -> aSa | bSb | a | b | e
Example: - Derivation of sentence "ababa"
S => aSa
=> abSba
=> ababa
Don't you think that the way in which a TM crosses off the symbols for
palindrome "ababa" is related to the way in which the sentence is being
generated by the grammar?
No, he probably can't do it. Many problems involving Turing machines
are inherently undecidable, and among them is the problem of deciding
whether a Turing machines accepts the language generated by a given CFG
(insert trivial proof by reference to Rice's theorem here). In other
words, the relationship between a given Turing machine and a given
context-free grammar can be so complex that there exists no algorithm
that can determine if they are related at all. It is possible to
construct an arbitrary phrase-structured grammar from a Turing machine,
but I guarantee that it will look nothing like the simple grammar for
palindromes that you've given above. This approach is a dead-end.
Don't you think that you went slightly off-topic from suggestion of
transition table for language (a^n)(b^2n)(c^n) to Rice Theorem,
Undecidability ...??
.
- Follow-Ups:
- Re: Question about Programming a Turing Machine
- From: Chris Smith
- Re: Question about Programming a Turing Machine
- References:
- Question about Programming a Turing Machine
- From: rhaazy
- Re: Question about Programming a Turing Machine
- From: frame
- Re: Question about Programming a Turing Machine
- From: Chris Smith
- Question about Programming a Turing Machine
- Prev by Date: Re: divide polynominal equation???
- Next by Date: Re: Challenge Algorithm
- Previous by thread: Re: Question about Programming a Turing Machine
- Next by thread: Re: Question about Programming a Turing Machine
- Index(es):
Relevant Pages
|
