# Derive Turing Machine with high level description

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?

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.