Answer

(a) is the set of strings of even length consisting entirely of as. The corresponding machine has three states: the first means "I have seen an even number of as" (this state is the start state and also the unique accepting state); the second means "I have seen an odd number of states" and the third is an error state (a scowlie) to which you go if you receive any character other than an a;

(b) is the set of strings consisting of any number of copies of ab concatenated together. The corresponding machine has three states. The start state (which is also the unique accepting state). . .

(c) contains those strings consisting of as followed by a greater number of bs.


Back to exercises