Let us now consider an algorithm for determining whether a specific TG that has no A-edges accepts a given word.

Step I Number each edge in the TG in any order with the integers 1, 2, 3 . . . x, where x is the number of edges in the TG.

Step 2 Observe that if the word has y letters and is accepted at all by this machine, it can be accepted by tracing a path of not more than y edges.

Step 3 List all strings of y or fewer integers each of which ≤ x. This is a finite list.

Step 4 Check each string on the list in Step 3 by concatenating the labels of the edges involved to see if they make a path from a - to a + corresponding to the given word.

Step 5 If there is a string in Step 4 that works, the word is accepted.

If none work, the word is not in the language of the machine

(i) Prove this algorithm does the job.

(ii) Why is it necessary to assume that the TG has no A-edges?