4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – Knogger
    Commented Aug 2 at 19:07
  • $\begingroup$ 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$. $\endgroup$
    – Knogger
    Commented Aug 2 at 19:34
  • $\begingroup$ @Knogger Thank you for brining my attention. You right. $L$ is indeed supposed to regular. I added it. $\endgroup$
    – Daniel
    Commented Aug 2 at 20:10

1 Answer 1

Reset to default
4
$\begingroup$

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

As "there exist" can be specified by union of languages, and "and" can be specified by intersection of languages, we get that

$$ L' = \bigcup_{q\in Q, q_f\in F} L(A_{q_0, q}) \cap L(C_{q, q_f})$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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$$ $\endgroup$
    – Daniel
    Commented Aug 3 at 15:25
  • $\begingroup$ 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$$ $\endgroup$
    – Daniel
    Commented Aug 3 at 15:26
  • $\begingroup$ 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'$. $\endgroup$
    – Daniel
    Commented Aug 3 at 15:27
  • $\begingroup$ $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. $\endgroup$
    – Bader Abu Radi
    Commented Aug 3 at 16:33
  • $\begingroup$ 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''$. $\endgroup$
    – Bader Abu Radi
    Commented Aug 3 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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