Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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??

Thanks in advance

share|cite|improve this question
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
up vote 3 down vote accepted

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$.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.