Question

8. Give an implementation of the macroinstruction searchleft (a, qi, qi) which indicates that the machine is to search its tape to the lef 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 q. otherwise it is to go into state q

Answer 1

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)$

5GI. B) = (qi, B. S)

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

Here, S means stay i.e. don't move the head. Comment in case of any doubts.