classe di complessità di tempo

[St3llina_N3ra]

Ciao, spero di essere nella sezione giusta, mi scuso in caso contrario.
C'è qualcuno che studia informatica che sa come fare a dimostrare che se L è un linguaggio regolare allora appartiene a TIME(n+4)?
ho pensto che sia necessario dimostrare che time (n+4) contiene anche la classe dei linguaggi regolari e che il punto di partenza sia il numero di passi di computazione effettuati da un DFA per decidere una stringa di lunghezza n... ma come farlo?

[alka]

Originariamente inviato da St3llina_N3ra
Ciao, spero di essere nella sezione giusta, mi scuso in caso contrario.
C'è qualcuno che studia informatica che sa come fare a dimostrare che se L è un linguaggio regolare allora appartiene a TIME(n+4)?
ho pensto che sia necessario dimostrare che time (n+4) contiene anche la classe dei linguaggi regolari e che il punto di partenza sia il numero di passi di computazione effettuati da un DFA per decidere una stringa di lunghezza n... ma come farlo?

Hai già aperto anche questa discussione.