0
$\begingroup$

So I have been going over Turing machines for my revision and came across an old worksheet with the question:

Derive a Turing Machine using high level description with stages to decide on the following language {<π‘ͺ,𝒔>|π‘ͺ π’Šπ’” 𝒕𝒉𝒆 π‘ͺπ’‰π’π’Žπ’”π’Œπ’š π‘΅π’π’“π’Žπ’‚π’ π’‡π’π’“π’Ž 𝒕𝒉𝒂𝒕 𝒄𝒂𝒏 𝒑𝒓𝒐𝒅𝒖𝒄𝒆 𝒂 π’”π’•π’“π’Šπ’π’ˆ 𝒔}.

I thought I understood Turing machines and CNF until I came across this but I can't figure it out. There is no answer sheet for this so I was wondering could someone answer it with steps to guide me through it so I can understand?

$\endgroup$
0
$\begingroup$

Its easy to check that $C$ is given in Chomsky Normal Form, because you just have to iterate through the production rules and make sure each one of them satisfies the definitions for being a CNF production.

Then, the harder part is deciding whether $C$ can produce $s$ or not. Notice, that a CNF will derive a word with length $n$, in exactly $2n-1$ steps. (every production will either transform a variable to the letter corresponding to it, or will create one new variable) Keeping this in mind, we can just iterate through all production chains that contain $2n-1$ steps (for $n=|s|$), and check whether we saw $s$ or not. If $s\in L(C)$, then we will see it, since $s$ can be derived with $2n-1$ steps. And if $s\notin L(C)$ we won't see it, therefore the algorithm is correct.

$\endgroup$
2
  • $\begingroup$ You dont need to: "derive a turing machine using high level description [...]" $\endgroup$
    – nir shahar
    Apr 24 at 21:15
  • $\begingroup$ Glad that I can help! $\endgroup$
    – nir shahar
    Apr 24 at 21:22

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.