1
$\begingroup$

Let L is a regular language then is

L' = {x$_2$x$_1$| x$_1$x$_2$ ∈ L}

regular?

Thus x$_1$x$_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield regular language?

$\endgroup$
  • $\begingroup$ What is this "L is regular" inside the definition of $L$? Is this a recursive definition? functional definition of a language? $\endgroup$ – R B Jan 20 '15 at 12:47
  • $\begingroup$ it means if x$_1$x$_2$ is a regular language, then can x$_2$x$_1$ be a regular language? $\endgroup$ – Maha Jan 20 '15 at 12:49
  • $\begingroup$ Do you mean the following? If $L$ is a regular language, then is $\{x_1x_2 | x_2x_1\in L\}$ also regular? $\endgroup$ – Klaus Draeger Jan 20 '15 at 12:50
  • $\begingroup$ This isn't satisfying as a formal definition. What is $x_1?$ a string in $\Sigma^*$? How can you define a language $L$ when inside the definition you say "$L$ is regular"? $\endgroup$ – R B Jan 20 '15 at 12:50
  • 1
    $\begingroup$ That is an golden oldie: Prove that regular languages are closed under the cycle operator, an operation also known as rotation or conjugation. $\endgroup$ – Hendrik Jan Jan 20 '15 at 15:57
1
$\begingroup$

The answer is yes. Suppose $A=(Q,q_0,F,\delta)$ is a deterministic finite automaton (with set of states $Q$, initial state $q_0$, set of final states $F$, and transition function $\delta$) recognizing the original language $L$. Then you can construct a nondeterministic automaton for $L'$ as follows:

For each state $q$ of $A$ create a separate copy of $A$, add $\epsilon$-transitions from its accepting states to the initial state, and then make $q$ the initial and (unique) accepting state. This gives you an NFA $A_q=(Q,q,\{q\},T)$, with transition relation $T=\{r,a,\delta(r,a)|r\in Q,a\in\Sigma\}\cup\{(r,\epsilon,q_0)|r\in F\}$. This NFA accepts a word $w$ if and only if there is a decomposition $w=uv$ such that $\delta(q,u)\in F$ and $\delta(q_0,v)=q$, which implies $vu\in L$.

Let $A'$ be the union of all the $A_q$. Then for any $uv\in L$, $vu$ is accepted by $A_q$ for $q=\delta(q_0,u)$, and therefore by $A$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The language $L'$ is regular indeed.

Let $M$ be a DFA for $L$.

In order to prove it, build an NFA which "guesses" the state of the automaton $M$ after reading $x_1$.

In order to do so, create $|Q|$ copies of $M$ (for each state $q\in Q$, create a copy $M_q$), and a new initial state $q_0'$ with a $\epsilon$-transition to each state $q$ inside the sub-automaton $M_q$.

Next, we need that after reading $x_2$, the automaton will be able to read $x_1$, so add epsilon moved from each state $f\in F$ in $M_q$ to $M_q(q_0)$ (the copy of the initial state of $M$), and make $q$ the only accepting state of $M_q$.

(well, formally, in order to prevent accepting the empty word, if it wasn't a part of $L$, you'll need to create additional state $q'$ in $M_q$ so that $q'$ will not be an accepting state, and the initial transition from $q_0$ would go into $q'$).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Great minds think alike, I guess :) $\endgroup$ – Klaus Draeger Jan 20 '15 at 13:16
  • $\begingroup$ @KlausDraeger, lol, yeah, I wrote my answer, posted it, and saw you posted the same answer :). $\endgroup$ – R B Jan 20 '15 at 13:17

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