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$

1 Answer 1

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, 2021 at 21:15
  • $\begingroup$ Glad that I can help! $\endgroup$
    – nir shahar
    Apr 24, 2021 at 21:22

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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