An interleaving of two words w1 and w2 is a word obtained by inserting the characters from w1 into w2 in the order in which they appear in w1. Thus, for example, b0a1c is an interleaving of bac and 01. So are bac01 and ba0c1 for that matter.
We start with a brief exercise to check that you understand what an interleaving
is. Let w1 and w2 be two words having no characters in common.
(i) How many ways are there of interleaving w1 and w2 ?
(ii) Supply all the words that can be obtained by interleaving abc
with 01, and arrange them lexicographically, taking the characters
to be in the order 0 < 1 < a < b < c.
Now let L1 and L2 be regular languages. Let the interleaving of L1 and L2
be the set of words that can be obtained by interleaving words from L1 with
Suppose L1 and L2 are recognised by deterministic finite state machines ℳ1 and ℳ2. Explain how to obtain from ℳ1 and ℳ2 a
nondeterministic machine that recognises the interleaving of L1 and
L2.
One question one can always ask about a nondeterministic machine is: how badly does it fail to be deterministic? That is to say, if we know it is in state 𝞂, and we give it character c, how many different states might it go to? Of course if it is deterministic the answer is 1. For the moment one might call the maximal value this can take (as 𝞂 and c vary) the degree of nondeterminism of the machine.
A hint for this question is: what might the degree of nondeterminism be of the machine you are building?
It will probably help if you start by considering a simple case where L1 and L2 come from disjoint alphabets. What is the degree of nondeterminism in this case?
What can you say about the case where you are interleaving more than two languages?
Back: 4 Nondeterministic Machines