Inserting a regular language into other regular language

user_5323655 0
Viewed 248

Let L1 and L2 be the regular languages over the alphabet {a,b}. We define the language L3 as follows:

L3 = {pqr | pr ∈ L1, q ∈ L2}

L3 is obtained by inserting a string from L2 inside a string from L1. Is language L3 is still regular or not?

I am trying to solve this problem. Is it possible to prove this using string substitution property or homomorphism of regular language? Is there any better and easier way to prove this?

nfa dfa regular-language formal-languages
1 Answers

Here is a high-level description of a construction to show there is an NFA accepting L3.

Let M1 and M2 be minimal DFAs such that L(M1) = L1 and L(M2) = L2. Copy M1 so there are two copies, M1[1] and M1[2]. Copy M2 so there are |Q1| copies M2[1], M2[2], …, M2[|Q1|]. Also, number the states q1, q2, …, q|Q1| of M1. Now construct an NFA for M3 as follows:

  1. From state qk of M1[1], add a lambda/epsilon transition to the initial state of M2[k]
  2. From the accepting state(s) of M2[k], add lambda/epsilon transitions to state qk of M1[2]
  3. The accepting states are the accepting states of M1[2]
  4. The initial state is the initial state of M1[1].

This NFA reads some input and then nondeterministically jumps to an instance of M2. It then reads a string in M2 and jumps back to where it left off in the next copy of M1 where it can accept. This NFA has a number of states equal to 2|Q1| + |Q1| * |Q2|.

user_8472690
Related