PDA

Visualizza la versione completa : classe di complessitÓ di tempo


St3llina_N3ra
25-01-2012, 17:54
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
25-01-2012, 18:00
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 (http://forum.html.it/forum/showthread.php?s=&threadid=1493833).

Loading