Regular language demonstration

Question

Consider this function:

Faro(x,z) that assume value: z if x = ε and a.faro(z,y) if x = ay
So is a recursive function, and for instance we have as result of faro(00110, 0101) = 000110110

I have to demonstrate that if L and M are regular language on the same alphabet we have that faro(L,M) = {faro(x,z) | x is on L and z is on M} is regular.

I'm not sure which is the best method to demonstrate the result. I'm now studying this type of problem for the first time.

Is more convenient to create a DFA or use the pumping lemma?

Answer 1

It looks like what's going on here is that the faro function takes two strings and interleaves them: faro(a1a2a3...an, b1b2b3...bm) = a1b1a2b2a3b3...anbn...bm (assuming w.l.o.g. m >= n).

If you can demonstrate that semantic fact about the faro function to your and others' satisfaction, then producing a NFA that does the same thing seems to be within reach:

1. create four states in the NFA for each triple (q, q', s) where q is a state in L's DFA, q' is a state in M's DFA, and s is either L, M, L' or M';
2. make the start state (q0, q0', L) to signify that we will start reading according to L's DFA with the possibility of alternating still available
3. probably, the accepting states are just those where q is accepting in L's DFA and q' is accepting in M's DFA... but I will let you work through the details here
4. the transitions will work as follows:

• When you see symbol a in state (q, q', L), then go to states (w, q', M) and (w, q', L'), where L's DFA transitions from q to w on a. This means we can either accept the next interleaved symbol of the string from M, or we can just read the rest of the string from L without a possibility of taking any more of the string from M

• When you see symbol a in state (q, q', M), go to states (q, w', L) and (q, w', M'), similar to above

• When you see symbol a in state (q, q', L'), go to state (w, q', L'); remember, L' means we gave up on reading interleaved symbols from the string in M

• When you see symbol a in state (q, q', M'), go to the state (q, w', M'), similar to the above

This is an NFA so if at least one path through accepts, the string is accepted. This is as it should be since if a string can be interpreted as some result of faro(x, y) for x in L and y in M, our NFA should accept it. Our NFA works by keeping track of:

1. how much of x has been read so far, by the component q in (q, q', s)
2. how much of y has been read so far, by the component q' in (q, q', s)
3. whether we need to read a symbol from x or y next, by the component s in (q, q', s)
4. whether we will subsequently be able to read from x or y, by the component s in (q, q', s)

I think the next steps are probably doing a couple of simple examples to see whether this construction works and, if so, then proceeding to prove that this NFA's language is the one desired (a proof by induction would be a good idea here). Once you prove there's an NFA for your language, you're done.