Derive Turing Machine with high level description

Question

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?

Answer 1

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.