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$
  • $\begingroup$ The line after "here is my attempt" is wrong. $\endgroup$ – gnasher729 Aug 31 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 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 at 20:10
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, privacy policy and cookie policy

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