Answer: Finite automata

Question: Find a finite automaton that accepts strings from the alphabet a, b, c, and d which contain at least one a, one b, and one c.

Answer: I'll write a transition table over states where a letter is capitalized if it has been found. (So aBC represents that we've found b and c so far in the string.) The start state is abc, and the accepting state is ABC.

             input
state   a    b    c    d
abc    Abc  aBc  abC  abc
abC    AbC  aBC  abC  abC
aBc    ABc  aBc  aBC  aBc
aBC    ABC  aBC  aBC  aBC
Abc    Abc  ABc  AbC  Abc
AbC    AbC  ABC  AbC  AbC
ABc    ABc  ABc  ABC  ABc
ABC    ABC  ABC  ABC  ABC


Answer / Finite automata / Review questions / 15-211 A, B