Algorithm 01
Keep two binary flags, the a-flag and the b-flag. Every time an a is read, the a-flag is reversed (0 to 1, or 1 to 0); and every time a b is read, the b-flag is reversed. We start both flags at 0 and check to be sure they are both 0 at the end.
4 characters • only a and b accepted
Try an example
A-FLAGtoggles on “a”
A0
B-FLAGtoggles on “b”
B0
FINAL RESULT
Valid
PROCESS TRACE
Algorithm 02
Keep one binary flag called the type3-flag. Read the letters two at a time. If both letters are the same, leave the flag unchanged because they form a type1 or type2 factor. If the two letters differ, reverse the type3-flag. The input is valid when the flag starts at 0 and ends at 0.
4 characters • pairs are read from left to right
Try an example
LETTER PAIRStwo at a time
TYPE3-FLAGtoggles on different pairs
F0
FINAL RESULT
Valid
PAIR TRACE