$L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

$$\Sigma=\left \{ a,b,c \right \}$$.

For a string $$w\in \Sigma^*$$, $$Drop_a(w)$$ is the string $$w$$ after we remove all occurrences of "a" from it.

The question asks to show that if $$L$$ is a regular language, then $$L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$$ is a regular language.

What I tried

$$L$$ is regular, thus $$L=L(A):A=(\Sigma,Q,q_0,F,\delta_A)$$

$$Drop_a(L)=L(B) :B=(\Sigma,Q,q_0,F,\delta_B)$$ s.t

$$\delta_B(q,\sigma)=\delta_A(q,\sigma) , q\in Q,\sigma \in\left \{ b,c \right \}$$

$$\delta_B(q,\varepsilon)=\delta_A(q,a), q\in Q$$

For each $$p,q\in Q$$, let $$A_{p,q}$$ be the automaton $$A$$, except that initial state is $$p$$ and final state is $$q$$.

Finally, we can use the closure properties of regular languages: $$L'=L(A)\cap\left \{ \bigcup_{\begin{matrix} q\in Q\\ f\in F \end{matrix}}L(A_{q_0,q})\cup L(B_{q,f}) \right \}$$

(This is my attempt to use the technique @Hendrik Jan used to answer this post.)

Alternatively, $$L'=L(A)\cap\left \{ L(A)\cdot L(B) \right \}$$

I can't decide if any of this attempts is correct.

• Hi, maybe I missed it, but I think $L$ isn't defined in the problem. Is $L$ supposed to be an arbitrary regular language over $\Sigma$? Commented Aug 2 at 19:07
• Just an observation, in both solutions you're cutting with $L$. But $L'$ isn't necessarily a subset of $L$, take for example $L = (bb)^+$, then $L' = b^+ \supset L$. Commented Aug 2 at 19:34
• @Knogger Thank you for brining my attention. You right. $L$ is indeed supposed to regular. I added it. Commented Aug 2 at 20:10

Note that a word $$w$$ is in $$L'$$ iff there exist states $$q\in Q, q_f\in F$$ such that $$q_0 \xrightarrow{w} q$$ and $$q \xrightarrow{drop(w)} q_{f}$$, where the latter runs are runs in $$A$$. The first run is captured by the automaton $$A_{q_0, q}$$ in the sense that it exists iff $$A_{q_0, q}$$ accepts $$w$$. Now we need to design an automaton that captures the second run, namely an automaton that accepts a word $$w$$ iff $$q \xrightarrow{drop(w)} q_{f}$$ is a run in $$A$$. Note that $$B_{q, q_f}$$ does not do the job as the needed automaton should be able to read also $$a$$'s and still be able to reach a state in $$F$$, yet yours does not. A good candidate is an automaton $$C_{q, q_f}$$ that operates as $$A_{q, q_f}$$ except that when it reads $$a$$, it stays in the same state (that is, we replace all $$a$$-transitions with self-loops labeled with $$a$$ in the automaton $$A_{q, q_f}$$).
$$L' = \bigcup_{q\in Q, q_f\in F} L(A_{q_0, q}) \cap L(C_{q, q_f})$$
• Hello! I'm failing to understand something: Suppose that $$L=L(A)=\left \{ abacbabcb,w \right \}$$ s.t $$|w|$$ is odd and doesn't have "a". If I understand corectly, $$L'=\left \{ abacba \right \}$$ In $A$ , we can see w.l.o.g the path $$q_0\overset{a}{\rightarrow}q_1\overset{b}{\rightarrow}q_2\overset{a}{\rightarrow}q_3\overset{c}{\rightarrow}q_4\overset{b}{\rightarrow}q_5\overset{a}{\rightarrow}q_6\overset{b}{\rightarrow}q_7\overset{c}{\rightarrow}q_8\overset{b}{\rightarrow}q_f$$ Commented Aug 3 at 15:25
• and in $C$ this path becomes: $$\underset{a}{q_0} \; \; \; \; q_1\overset{b}{\rightarrow}\underset{a}{q_2} \; \; \; \;q_3\overset{c}{\rightarrow}q_4\overset{b}{\rightarrow}\underset{a}{q_5} \; \; \; \; q_6\overset{b}{\rightarrow}q_7\overset{c}{\rightarrow}q_8\overset{b}{\rightarrow}q_f$$ Commented Aug 3 at 15:26
• my question is why you didn't write $$L'' = \bigcup_{q\in Q, q_f\in F} L(A_{q_0, q}) \cdot L(C_{q, q_f})$$ In this example, the $q$ in $L''$ is $q_3$. I don't see which $q$ you should choose for $L'$. Commented Aug 3 at 15:27
• $L''$ is the language of words $w$ such that $w = u\cdot v$ where $q_0 \xrightarrow{u }q$ and $q \xrightarrow{v} q_f$. However, that does not mean that $w=u$ and $v = drop(u)$ as required by $L'$. The intersection enforces that $w$ is such that $w\cdot drop(w)$ is accepted by $A$ as we have a conjunction of conditions, where each condition is applied on $w$ separately. I did not look at the specific example you wrote. In general, if it worked on an example, it does not mean that it is correct. If you insist on discussing an example, we can move to a chat room. Commented Aug 3 at 16:33
• I encourage you to try and prove the expression in the question first. Then, read my previous comment and try to come up with a counter-example for $L''$. Commented Aug 3 at 16:46