1
$\begingroup$

Let $L$ be a language over $\Sigma=$ {$a,b,c$}

We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$.

Let $T(L)=${$ T(w) : w\in L$}, we need to show that if $L$ is regular, than so is $T(L)$.

I've came to mind of an approach, which consists of claiming there is a DFA/NFA $M_L$ that accepts $L$, constructing a DFA/NFA $M_{T(L)}$ that works for $T(L)$ and proving it's correctness, and then proving that $L(M_L)=L(M_{T(L)})$ by showing two-way inclusion. (basically $\subseteq$ and "the other way around").

Thing is, I feel that this approach is overdoing it, and that there is a shorter "path" to prove this.

Unsure in which direction to take this.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

If $L$ is regular then it has a NFA $M_L$. I think you can answer your problem if you can answer the following:

  • If for all $w \in L$, $w$ has no $a$, then what would can you say about the elements of $T(L)$?
  • If for some $w \in L$, $w$ has an $a$ then there must be some transition in $M_L$ that consumes an $a$. Now, if all instance of $a$ is removed in all $w \in L$, what happens to the transitions in $M_L$ that consumes an $a$?
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ regarding first question, in that case than $L=T(L)$. About the second question, I assume we would change all $a$ transitions in $M_L$ to $\epsilon$ transitions? $\endgroup$
    – Aishgadol
    Commented Mar 25, 2023 at 15:27
  • $\begingroup$ You just need to prove that changing $a$ to $\varepsilon$ will recognize $T(L) $. $\endgroup$
    – Russel
    Commented Mar 26, 2023 at 2:15
  • $\begingroup$ I see, which approach would you choose to prove this? is this a two-way inclusion? I'm not sure how to approach proofs on DFA/NFA/regular languages, except for induction, I was not introduced (yet) to different approaches $\endgroup$
    – Aishgadol
    Commented Mar 26, 2023 at 7:51
1
$\begingroup$

No, you are not overdoing this. Formally all these steps need to be established. In practise the equivalence step might be skipped, when the constructed automaton "obviously" is doing what it is claimed to do.

On the other hand a formal proof is not that hard. The new automaton might be one where the letter $a$ is replaced by the empty word $\varepsilon$. Now there is a one-to-one correspondence between computations of the two automata, which helps formalities.

Another option might be to work with regular expressions. If you have an expression for $L$, then the expression for $T(L)$ is found by deleting $a$'s. Intuitively clear. The formal proof would need a proof with induction (on the structure of the expression) I guess.

By the way. Your closure property is a special case of closure under homomorphisms.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I see. What do you mean by my closure property? Is that the property I'm trying to prove? $\endgroup$
    – Aishgadol
    Commented Mar 25, 2023 at 15:29

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.