Come dimostrare per contraddizione che ogni linguaggio ereditario non vuoto contiene la stringa vuota?

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

  •  05-11-2019
  •  | 
  •  

Domanda

Una lingua L è chiamata ereditaria se ha la seguente proprietà:

Per ogni stringa non vuota X in L, c'è un carattere in x che può essere eliminato da X per dare un'altra stringa in L.

Dimostrare per contraddizione che ogni linguaggio ereditario non vuoto contiene la stringa vuota.

Ecco il mio tentativo:

Per dimostrare per contraddizione, supponiamo che per ogni stringa non vuota X in L, non esiste un carattere in X che può essere eliminato da X per dare un'altra stringa in L.

Ciò significa che se un carattere in x viene eliminato una stringa vuota viene lasciata. Poiché una stringa vuota è anche una stringa, ogni linguaggio ereditario non vuoto contiene la stringa vuota.

Non sono esattamente sicuro di come provi per contraddizione. Qualcuno può aiutare a rivedere questo?

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top