If $L$ is regular, then $L' = \{ x\#y \, |\, yx \in L \}$ is regular.

Question

If $L$ is regular, then $L' = \{ x\#y \, |\, yx \in L \}$ is regular. Assume that no word in $L$ contains $\#$.

I think this is true. But I want to prove this without construction. Here is what I have so far:

$pref(L)$ which is the language of all prefixes of $L$ is regular, we proved this in class.

$suff(L)$ which is the language of all suffixes of $L$ is regular, we proved this in class.

The language $\{\#\}$ is regular because there is a regular expression that describes it: $(\#)$.

Now I know that the language $suff(L) \, \circ \{\#\} \, \circ pref(L)$ is regular, but this is not $L'$.

Any directions?

You can maybe use the fact that, if $L$ is regular then it exists a finite double family $(L_i^{(1)},L_i^{(2)}){i\in [1\cdots n]}$ s.t. $$ \langle L | uv\rangle=\sum{i=1}^n \langle L_i^{(1)} | u\rangle\langle L_i^{(2)} | v\rangle $$ where $\langle L | w\rangle=[w\in L]$ i.e. $1$ iff $w\in L$ $0$ otherwise. — Duchamp Gérard H. E., Dec 05 '17 at 15:46
We haven't covered double families yet... Is there another solution? — UFC Insider, Dec 05 '17 at 15:48

score 1 · Answer 1 · edited Sep 19 '19 at 15:41

We can construct a suitable automaton from an automaton fo $L$:

First (i.e., before we encounter "#"), we keep track of which intermediate states might have led to which current states, that is: If the automaton for $L$ has state set $S$, we now need $S^S$, i.e., a new state is a map $S\to S$; the initial state is the identity map, and each input character lets the original automaton act pointwise on the input function. This way, the "current" function describes which state we would be in if we had started in state $s$.

When we encounter "#", the state $f$ is turned into a pair consistng of the initial state of the original automaton and $f^{-1}$ of the set of accepting states, and from now on we apply the original automaton to the first component.

Accepting states are precisely those pairs $(a,A)$ with $a\in A$.

I don't understand... But thank you for the time – UFC Insider Dec 05 '17 at 16:03 — UFC Insider, Dec 05 '17 at 16:03

If $L$ is regular, then $L' = \{ x\#y \, |\, yx \in L \}$ is regular.

1 Answers1