# 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.