0
$\begingroup$

For example, how could I prove that the following language is deletion closed:

{$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0}

The reason seems obvious to me, I just can't see a way to prove it.

$\endgroup$
  • 2
    $\begingroup$ If you can't prove it it's not obvious. What have you tried and where did you get stuck? (What is "deletion closed"?) $\endgroup$ – Raphael Nov 21 '15 at 20:02
  • 2
    $\begingroup$ I encourage you to edit the question to include the definition of "deletion closed" in the question. $\endgroup$ – D.W. Nov 21 '15 at 22:29
3
$\begingroup$

You'd prove that a language $L$ is deletion-closed as follows.

Consider a word $w\in L$ and let $w = w_1\dots w_\ell$. Now, for any $r$ and $s$ with $1\leq r\leq s\leq \ell$, consider the word $w' = w_1\dots w_{r-1}w_{s+1}\dots w_\ell$, i.e., the word that results from deleting the substring $w_r\dots w_s$ from $w$. We have $w'\in L$ because [some argument that will be specific to the language $L$ you're working with].

| cite | improve this answer | |
$\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.