Italian subtitles

← cs262_unit1_32_s_nondet-to-det

risposta da non-deterministica a deterministica

Get Embed Code
4 Languages

Subtitles translated from English Showing Revision 1 created 06/05/2012 by lorenz.mh.

  1. Bhè, facciamoci un po' di spazio e lavoriamoci su.
  2. Ci sono solo una,due,tre lettere coinvolte: 'a' 'b' 'c' ,
  3. quindi vediamole una per una.
  4. Supponiamo che sia nello stato '2456' e vedessi una 'a' .
  5. Se sono in due e vedo una 'a' la macchina termina, in quattro termina,
  6. in cinque con 'a' termina, in sei lo stesso.
  7. Non va bene.
  8. '2456' con 'a' la macchina fallisce il suo compito.
  9. Non arriva a '23' .
  10. Bene, e se vedo una 'b' ?
  11. Se sono in due e vedo una 'b' , vado in tre. Che sembra buono.
  12. quattro ed una 'b' la macchina termina.
  13. cinque ed una 'b' vado in due.
  14. sei ed una 'b' la macchina termina.
  15. Oh, 'b' ci porta esattamente a due e tre.
  16. '2456' con 'b' va a due e tre.
  17. Consideriamo 'c' per vedere se abbiamo dimenticato qualcosa.
  18. Sono in '2456' .
  19. da due con 'c' non vado in nessun posto.
  20. da quattro con 'c' nemmeno.
  21. da cinque con 'c' vado a sei,
  22. e da sei con 'c' non vado da nessuna parte, quindi '2456'
  23. con 'c' va a sei.
  24. Abbiamo già definito questo vertice: '2456' con 'c' va a sei,
  25. e poiché la macchina è deterministica volgiamo che ci sia un unico
  26. vertice con 'c' .
  27. Sembra che 'b' sia la risposta giusta.
  28. L'etichetta per questo vertice è 'b' .
  29. Adesso, questa non è una prova,
  30. ma abbiamo appena visto come una macchina non-deterministica
  31. possa essere convertita in una deterministica
  32. usando esattamente gli stessi stati.