# proving by construction that language is regular

I had this exercise saying the following: $$L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\}$$ I need to prove that $L$ is regular by defining an automaton for it.

I thought that I'll duplicate $L_1$ twice and $L_2$ in the number of $L_1$'s states, and from every state in $L_1$ I'll do an epsilon transition to the starting state of his duplicate $L_2$, and from the finishing state of $L_2$ I'll do an epsilon transition to the right state in the duplicate of $L_1$, but it sounds like tons of states and impossible to define formally.

Any ideas??

-
Are we assuming that $L_1$ and $L_2$ are regular? – Brian M. Scott Nov 30 '12 at 12:04
Thanks for that :) I don't study this material in English but thanks :) – DanielY Nov 30 '12 at 12:04
yes, L1 and L2 are regular – DanielY Nov 30 '12 at 12:05

Let $M_1$ be a finite state automaton that recognizes $L_1$, and let $M_2$ be an FSA that recognizes $L_2$. Let $M_1'$ be a copy of $M_1$, except that it has no acceptor states. For each state $s$ of $M_1$ let $M_s$ be a copy of $M_2$, except that it has no acceptor states. From each state $s$ of $M_1'$ make an $\epsilon$-transition to the initial state of $M_s$, and from each state of $M_s$ that corresponds to an acceptor state of $M_2$ make an $\epsilon$-transition to $s$ in $M_1$. Call this new compound automaton $M$. The initial state of $M$ is the initial state of $M_1'$, and the acceptor states of $M$ are the acceptor states of $M_1$.

I’ll leave you to check that this works.

(The basic idea is that $M_s$ allows you to insert an $L_2$ word into any $L_1$ word that passes through state $s$ in $M_1$ at the point where it passes through $s$.)

Added: To get you started on the formal construction, let $M_1=\langle Q_1,\Sigma_1,\delta_1,q_0^1,F_1\rangle$ and $M_2=\langle Q_2,\Sigma_2,\delta_2,q_0^2,F_2\rangle$. Then $M$ will be $\langle Q,\Sigma_1\cup\Sigma_2,\delta,q_0^1,F_1\rangle$, where $Q$ and $\delta$ remain to be defined. $Q=(Q_1\times\{0,1\})\cup(Q_1\times Q_2)$; in terms of my informal description above, the states in $Q_1$ are the states of $M_1$, the states in $Q_1\times\{0\}$ are the states in $Q_1$, the states in $Q_1\times\{1\}$ are the states in $M_1'$, and for each $s\in Q_1$ the states in $\{s\}\times Q_2$ are the states of $M_s$. All that remains is to build $\delta$ from $\delta_1$, $\delta_2$, and the desired $\epsilon$-transitions; see if you can do that, now that you have the complete set of states of $M$. For instance, for each $s\in Q_1$ you’ll want an $\epsilon$-transition from $\langle s,1\rangle$ to $\langle s,q_0^2\rangle\in \{s\}\times Q_2$, and for each $s\in Q_1$ and $t\in F_2$ you’ll want an $\epsilon$-transition from $\langle s,t\rangle$ to $\langle s,0\rangle$. (Note that I am assuming that $0,1\notin Q_2$.)

-
That what's I thought, but isn't that a huge amount of states? and how would you define it as 5-tuple(Q, sigma, delta, q0, F)? – DanielY Nov 30 '12 at 12:18
@user1067083: If $M_1$ has $n_1$ states, and $M_2$ has $n_2$ states, $M$ has $n_1(n_2+1)$ states. I don’t see any problem in defining the $5$-tuple; where are you having difficulty? – Brian M. Scott Nov 30 '12 at 12:22
How would you define Q, for instance? it's Q1 union what? – DanielY Nov 30 '12 at 12:33
@user1067083: See the addition that I just made; is it enough to get you going? – Brian M. Scott Nov 30 '12 at 12:37
@user220688: Good catch: that was an oversight on my part. I’ve fixed it now. Thanks very much. – Brian M. Scott Mar 28 '15 at 22:23