0
$\begingroup$

A language L is called hereditary if it has the following property:

For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L.

Prove by contradiction that every nonempty hereditary language contains the empty string.

Here's my attempt:

To prove by contradiction, we assume that for every nonempty string x in L, there is no character in x which can be deleted from x to give another string in L.

This means that if a character in x is deleted an empty string is left. Since an empty string is also a string, every nonempty hereditary language contains the empty string.

I'm not exactly sure how to proof by contradiction. Can someone help review this?

$\endgroup$
3
  • $\begingroup$ The line after "here is my attempt" is wrong. $\endgroup$
    – gnasher729
    Aug 31, 2019 at 19:56
  • $\begingroup$ The second line is a non sequitur. What follows from the first (incorrect) line is that if a character in x is deleted, the result is not in L. $\endgroup$
    – gnasher729
    Aug 31, 2019 at 20:09
  • $\begingroup$ You say "This means that if a character in x is deleted an empty string is left". So the string has exactly one character??? $\endgroup$
    – gnasher729
    Aug 31, 2019 at 20:10

1 Answer 1

0
$\begingroup$

Let L be a nonempty hereditary language. Let x be one of the shortest strings in L. x exists because L is not empty.

Removing any character from x would produce a string not in L, since x is one of the shortest strings. Because L is hereditary, we can remove a character from x giving another string in L, unless x is the empty string. Therefore x is the empty string. Therefore L contains the empty string.

If you insist on proof by contradiction: Let L be a nonempty hereditary language not containing the empty string, and let x be one of the shortest strings in L. x is not the empty string since L doesn't contain the empty string. Therefore there is a character in x which can be removed, giving a string y in L.

But y is shorter than x, therefore x is not the shortest string in L.

$\endgroup$

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.