1
$\begingroup$

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

  • 0
    yes, L1 and L2 are regular2012-11-30

1 Answers 1

3

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

  • 1
    @user220688: Good catch: that was an oversight on my part. I’ve fixed it now. Thanks very much.2015-03-28