Some applications of a technique of Sakoda and Sipser
Bala Ravikumar · ACM SIGACT News · 1990
Sakoda and Sipser [Sa78] introduced a technique for constructing certain regular languages over a large alphabet and used these languages as candidates for proving lower bounds on the size increase when converting a nondeterministic finite automaton (NFA) to a deterministic one (DFA). The purpose of this note is to show that their method is quite useful in solving several problems in the theory of regular languages. In view of its intuitive appeal, we recommend it as a pedagogic aid for presenting lower bound proofs.