5
$\begingroup$

For a language $\mathcal{L}$ over an alphabet $\Sigma$, define

$$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$

How can I prove that if $\mathcal{L}$ is regular, then $\mathcal{SW(L)}$ is also regular?

$\endgroup$
3
  • 1
    $\begingroup$ What does "SW" mean? $\endgroup$ May 11 at 14:53
  • $\begingroup$ "SW" comes from "SandWich", I guess. $\endgroup$
    – John L.
    May 11 at 18:35
  • $\begingroup$ Is it that $sw(\sigma)$ denote the "Shortest Word generated by $\sigma$ (if it exists) and if there are several, $sw(\sigma)$ is the lexicographically first of those"? Taken from Page-46 of this PDF. $\endgroup$ May 31 at 23:36

3 Answers 3

4
$\begingroup$

Take a DFA $(Q,\Sigma,\delta,q_0,F)$ accepting $\mathcal{L}$. We can associate each word $x \in \Sigma^*$ with a function $\delta_x\colon Q \to Q$ given by $\delta_x(q) = \delta(q,x)$. In other words, if the DFA is at state $q$ and it reads the word $x$, then it reaches state $\delta_x(q)$. Let $\Delta = \{ \delta_x : x \in \Sigma^* \}$.

A word $y$ is in $\mathcal{SW}(\mathcal{L})$ if there exists $x \in \Sigma^*$ such that $(\delta_x \circ \delta_y \circ \delta_x)(q_0) \in F$. Hence in order to determine whether $y \in \mathcal{SW}(\mathcal{L})$, it suffices to maintain $\delta_y$, which can be done using a DFA whose set of states is $Q^Q$. I leave the rest of the details to you.

$\endgroup$
3
  • $\begingroup$ Hey Yuval, can you explain what exactly is $\delta_x(q)$? Toda! ;) $\endgroup$
    – Math4me
    Jun 17 at 9:34
  • $\begingroup$ $\delta_x(q) = \delta(q,x)$. $\endgroup$ Jun 17 at 10:14
  • $\begingroup$ Oh I missed that, thanks! $\endgroup$
    – Math4me
    Jun 17 at 10:15
3
$\begingroup$

Idea: Suppose we have an NFA $(Q, \Sigma, \Delta, I, F)$ for $\mathcal{L}$. To build an NFA for $\text{SW}(\mathcal{L})$, our plan is to make a separate copy of the states of the NFA for each candidate start state $q$, where that machine reads in $y$ and checks whether it is possible for some $x$ to (i) get from an initial state $I$ to the candidate start state $q$ on $x$, (ii) get from $q$ to $q'$ on $y$, and (iii) read in the same string $x$ to get from $q'$ to an accepting state in $F$. Formally, the states of the new NFA are $Q \times Q$ (one copy of $Q$ for each possible start state $q \in Q$), and our new NFA is $$ (Q \times Q, \Sigma, \Delta', \{(q, q) \mid q \in Q\}, F') $$ where $F'$ is defined formally as $$ F' = \{(q, q') \in Q \times Q \mid \exists x: q \in \Delta(I, x) \text{ and } \Delta(q', x) \cap F \ne \varnothing. $$

Note that the set $F'$ is a finite set -- we can just enumerate all the pairs in $Q \times Q$ and determine whether they are in $F'$ or not.

The definition of $\Delta'$ will be straightforward as it is the same for each copy of the original automaton.

Then we have to carefully argue two things (left as an exercise):

  1. If $w \in \text{SW}(\mathcal{L})$, then there is an accepting run of the new automaton on $w$.

  2. If there is an accepting run of the new automaton on $w$, then $w \in \text{SW}(\mathcal{L})$.

$\endgroup$
2
  • 1
    $\begingroup$ Nice! For me the interesting discovery is of course that the prefix/suffix string $x$ itself is no longer important, just the proper pairs $(q,q')$. Note that it is not necessary to explictly construct a new automaton if we use closure under union of regular languages for $A_{qq'}=(Q,\Sigma,\Delta,\{q\},\{q'\})$. $\endgroup$ May 11 at 20:52
  • $\begingroup$ @HendrikJan Indeed -- the "summary" of the prefix/suffix string in $(q, q')$ is the key idea. $\endgroup$
    – 6005
    May 12 at 4:25
1
$\begingroup$

If $L$ is a language of $A^*$ and $u, v$ are words, let $$ u^{-1}Lv^{-1} = \{ x \in A^* \mid uxv \in L \} $$ It is a well-known fact that if $L$ is regular, then every language $u^{-1}Lv^{-1}$ is regular and the set $\{u^{-1}Lv^{-1} \mid u, v \in A^*\}$ is finite. In particular, the subset $\{u^{-1}Lu^{-1} \mid u \in A^*\}$ is finite. Now observe that $$ SW(L) = \bigcup_{u \in A^*} u^{-1}Lu^{-1} $$ to conclude that $SW(L)$ is regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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