Question

8. Give an implementation of the macroinstruction searchleft (a, ,), which indicates that the machine is to search its tape to the left of the current position for the first occurrence of the symbol a. If an a is encountered before a blank, the machine is to go into state qi, otherwise it is to go into state q

Answer 1

Answer:-

The macro instruction can be broken down as follows: look at the tape symbol. If it matches , go to state $q_i$ . If it matches a blank, which is denoted by , go to $q_j$ . Otherwise, keep moving left and do not change the state.

Hence, let the state when the macro starts is . The transitions are:

$\delta(q, a) = (q_i, a, S)$

$\delta(q, \gamma) = (q, \gamma, L), \gamma \neq a, B$ .

Here, S means stay i.e. don't move the head.