Italian subtitles

← cs262_unit1_32_q_nondet-to-det

domanda da non-deterministico a deterministico

Get Embed Code
4 Languages

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

  1. Facciamo pratica
  2. nel convertire le macchine non-deterministiche in deterministiche.
  3. Ho scritto qui una macchina non-deterministica.
  4. c'è ambiguità al suo interno.
  5. Dallo stato uno ci sono due vertici che escono con 'a'.
  6. Ci sono inoltre epsilon transizioni,
  7. comincerò a costruire il suo equivalente deterministico qui sotto.
  8. Bhé, quando accendiamo la macchina non-deterministica,
  9. non possiamo che essere allo stato uno, dopo questo potremmo vedere una 'a' ,
  10. e se vedo una 'a' potrei essere in due o quattro,
  11. o prendere la epsilon gratis ed arrivare a cinque.
  12. O continuare e prendere la epsilon gratis fino a sei.
  13. Chiamerò questo nuovo stato '2456'
  14. poiché tiene traccia di ovunque possa andare il mio dito
  15. se simulassi questa macchina non deterministica.
  16. Adesso, questo stato dovrebbe essere accettante o no?
  17. Bhé, ricordate che una macchina a stati finiti accetta l'input se c'è un qualsiasi percorso
  18. che raggiunge uno stato accettante, e il sei è uno stato accettante.
  19. La macchina, in origine, poteva accettare 'a' ,
  20. 'a' , epsilon, epsilon, accetta. Vogliamo che la nostra macchina accetti anche 'a' .
  21. 'a', accetto.
  22. Nel mio mondo convertito, lo stato è accettante se almeno uno dei corrispondenti
  23. stati originali è accettante.
  24. Diciamo che sono in due, quattro,cinque o sei e vedo una 'c' .
  25. Se sono in due e vedo una 'c' , la macchina si interrompe.
  26. Se sono in quattro, si interrompe.
  27. Cinque, vado in sei, sembra buono.
  28. sei, si interrompe.
  29. Quindi se sono in due, quattro,cinque o sei e vedo 'c' ,
  30. finisco in sei, che è uno stato accettante.
  31. Adesso, c'è un altro modo per uscire da due, quattro, cinque e sei,
  32. e se usciamo, potremmo essere nel due o nel tre.
  33. Visto che tre è uno stato accettante,
  34. tre lo è anche qui sotto.
  35. Se sono in due o tre, e vedo una 'b', da due vado a tre,
  36. con 'c' terminerei, quindi finiamo nello stato tre.
  37. Se sono in due o tre e vedo 'c' ,
  38. devo per forza essere nello stato tre, e lo sono,
  39. quindi con 'b' o 'c' finiamo nello stato tre,
  40. che è anch'esso accettante.
  41. E se sono in tre, c'è un self-loop in tre.
  42. Adesso ho quasi completato gli stati dell'equivalente deterministico.
  43. Ho dimenticato di assegnare un'etichetta ad un vertice.
  44. Aiutatemi.
  45. Come quiz vorrei che poneste questo vertice,
  46. così che l'equivalente deterministico e la macchina non-determinisitica
  47. accettino lo stesso linguaggio.