turing 82.0 47.0 191.0 -51.0 284.0 -145.0 713.0 -55.0 300.0 44.0 455.0 -151.0 256.0 210.0 Verifier i=i -20.0 277.0 Maybe 477.0 257.0 No 264.0 433.0 429.0 504.0 549.0 391.0 726.0 207.0 Verifier j=j 597.0 159.0 Yes 152.0 208.0 j!=0 1 5 C C R 0 13 R 12 13 S 14 7 R 11 12 L 5 3 c C R 1 2 b b R 0 7 b b S 6 13 R 2 3 c C R 4 0 A A S 3 6 L 3 6 d d L 12 8 b b L 9 11 d D R 10 11 d D R 3 4 a a S 11 7 A A S 2 5 C C R 12 8 d d S 6 8 c c S 6 8 a a S 1 3 c C R 7 9 b B R 14 14 C C L 14 14 A A L 14 14 b b L 6 6 A A L 6 6 C C L 4 4 a a L 3 3 b b L 3 3 c c L 3 3 C C L 9 10 C C R 11 11 D D L 11 11 d d L 11 11 C C L 11 11 b b L 11 11 B B L 12 12 B B L 12 12 D D L 12 12 C C L 12 12 A A L 6 14 b b L 0 1 a A R 5 5 C C R 0 0 A A R 2 2 b b R 1 1 a a R 7 7 A A R 9 9 b b R 10 10 C C R 7 7 B B R 10 10 D D R This Side Checks that N(a)=N(c) and also checks for well-formedness i.e. w in a*b*c*d*. 636.0 26.0 This Side Checks that N(b)=N(d) and controls final acceptance of the string (or rejection at the end) Well-formedness is already assured. 694.0 652.0 Accept Empty String 426.0 294.0 The verifiers work simply by going backwards and failing if there are any unmatched symbols that ought to be matched. 298.0 488.0 The general principle of operation is to replace the symbol with a marked counterpart when a pair is found, and then verify that there are no unmarked symbols before accepting. 149.0 640.0