Come dimostrare per contraddizione che ogni linguaggio ereditario non vuoto contiene la stringa vuota?
-
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