How to prove by contradiction that every nonempty hereditary language contains the empty string?

cs.stackexchange https://cs.stackexchange.com/questions/113256

  •  05-11-2019
  •  | 
  •  

Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top