Question: EXAMPLE 9 . 6 For = { 0 , 1 } , design a Turing machine that accepts the language denoted by the regular expression

EXAMPLE 9.6
For ={0,1}, design a Turing machine that accepts the language denoted by the regular expression 00**.
This is an easy exercise in Turing machine programming. Starting at the left end of the input, we read each symbol and check that it is a 0. If it is, we continue by moving right. If we reach a blank without encountering anything but 0, we terminate and accept the string. If the input contains a 1 anywhere, the string is not in L(00**), and we halt in a nonfinal state. To keep track of the computation, two internal states Q={q0,q1} and one final state F={q1} are sufficient. As transition function we can take
(q0,0)=(q0,0,R),
(q0,)=(q1,,R).
As long as a 0 appears under the read-write head, the head will move to the right. If at any time a 1 is read, the machine will halt in the nonfinal state q0, since (q0,1) is undefined. Note that the Turing machine also halts in a final state if started in state q0 on a blank. We could interpret this as acceptance of , but for technical reasons the empty string is not included in Definition 9.3.
MY QUESTION. I think the anwer is wrong. Because the given transition function could accept empty string(). Isn't it?
 EXAMPLE 9.6 For ={0,1}, design a Turing machine that accepts the

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!