Sipser Exercise 1.41


For languages and over the same alphabet , the perfect shuffle of and is:

We show that for regular languages and , is also regular.


Let and be DFAs that accept and , respectively. We construct a machine that accepts .

Let . Take . Take .

Finally, define:

So alternates between advancing a copy of machine and , keeping track of which machine to advance with and . So accepts , and is regular.