= Shuffle of formal languages
{title2=$L_1\oplus L_2$}
= Interleaving of formal languages
{synonym}
The shuffle of two <formal languages> consists of <words> whose positions can be partitioned into two subsequences, each preserving its order, with the two resulting <words> belonging to the respective languages. For <regular languages>, a product-state <nondeterministic finite automaton> advances exactly one coordinate for each letter. Common letters allow either choice; the <powerset construction> proves closure.
Back to article page
