Italian subtitles

← cs262_unit1_31_l_nondeterminism

dummy description

Get Embed Code
5 Languages

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

  1. Queste semplici da scrivere FSM che stiamo usando
  2. coinvolge le transizioni epsilon ovvero l'ambiguità --
  3. ricordate: ambiguità significa che posso andare in due posti differenti con lo stesso input --
  4. sono dette macchine a stati finite non-deterministiche.
  5. Non-deterministiche significa qui che potreste non sapere con esattezza
  6. dove andare, ovvero dove posare il dito.
  7. I passi non sono tutti definiti. Avete delle scelte.
  8. Avete libertà.
  9. Una macchina senza passi definiti, senza epsilon transizioni
  10. e senza ambiguità è chiamata macchina a stati finiti deterministica.
  11. Tutto è determinato dall'inizio.
  12. Data la macchina e l'input, saprete sempre
  13. esattamente cosa succederà al suo interno.
  14. Il nostro simulatore di macchine a stati finiti può gestire
  15. macchine deterministiche.
  16. Questo lo rende molto utile per implementare le espressioni regolari
  17. dietro le quinte.
  18. Lasciatemi fare un esempio di questo non-determinismo per capirlo meglio.
  19. Supponete di essere ancora con questa macchina a stati finiti,
  20. ma adesso l'input è '1-23' .
  21. Dove siamo?
  22. Cominciamo da qui, e con '1' andiamo qui,
  23. e poi se siamo ancora in vita probabilmente vedremo un trattino,
  24. dobbiamo per forza essere passati di qua ed aver incotrato un trattino.
  25. E adesso c'è un '2' , e non è così ovvio.
  26. Posso rimanere qui per un self-loop con '3' ,
  27. o posso andare indietro e riprendere questa epsilon gratis
  28. e posso fare un self-loop qui con un '3'; potrei essere nello stato due o nel cinque.
  29. Se non c'è una sola risposta per dove potrei essere,
  30. allora il percorso è non-deterministico.
  31. Con un po' di contorno di divertimento, queste nozioni di determinismo
  32. o non-determinismo possono essere associate alla questione del libero arbitrio in filosofia.
  33. Possiamo compiere scelte indipendenti?
  34. O è tutto preordinato dallo stato corrente del mondo?
  35. e dalle forze agenti su di esso, come un gioco in sequenza come lo snooker o il biliardo?
  36. Alcuni filosofi avvicinano questo problema suggerendo che
  37. viviamo l'illusione del libero arbitrio -- pensiero sconcertante --
  38. poiché è utile per relazionarci con l'esperienza soggetiva.
  39. Spesso sentiamo di avere il libero arbitrio.
  40. Senza preoccuparci di quello che succede nel mondo reale,
  41. vedremo che un approccio del genere tiene anche
  42. parlando di macchine a stati finti.
  43. Anche se le macchine non-deterministiche sembrano concedere molto più
  44. potere e molta più libertà,
  45. tutto ciò che può essere fatto con loro, può essere fatto anche
  46. nel nostro "mondo deterministico nella palla da biliardo" .
  47. Infatti, potete vedermi estorcere libero arbitrio da questo mondo proprio in questo momento.
  48. Ogni macchina non-deterministica a stati finiti
  49. ha una corrispondente macchina deterministica a stati finiti
  50. che accetta esattamente le stesse stringhe.
  51. Le macchine non-deterministiche non sono affatto più potenti
  52. di quelle deterministiche.
  53. Sono solo più convenienti.
  54. E' facile dimostrarlo.
  55. Vediamo un esempio di questa straordinaria attestazione.
  56. Supponete di avere questa espressione regolare.
  57. Ci sono solo due stringhe nel linguaggio di questa espressione regolare,
  58. ma qui ho disegnato una macchina molto elaborata per rappresentarlo,
  59. che ha epsilon transizioni che gli sbucano dappertutto.
  60. Questa macchina è molto non-deterministica.
  61. Dobbiamo per forza vedere una 'a' , ma poi qui due transizioni epsilon
  62. rappresentano la scelta esplicita.
  63. Vado alla 'b' o passo oltre?
  64. La strada superiore, dovremmo in incontrare una 'b' .
  65. Su quella inferiore, saltiamo direttamente.
  66. In ogni caso vedremo 'c' .
  67. Scrivo ora una macchina deterministica
  68. che faccia esattamente la stessa cosa, e sottolineerò
  69. come avviene questa conversione.
  70. Lo vedremo in un momento.
  71. Dopo aver visto una 'a' , potrei essere in due,
  72. o posso prendere la epsilon ed essere in tre.
  73. Potrei avere preso la epsilon qui ed essere in sei
  74. o fino in fondo ed essere in quattro; quindi ci sono quattro posti
  75. in cui potrei essere.
  76. Sono un sacco di dita.
  77. Registrerò il nome del mio nuovo stato '2364' .
  78. Da qui, se vedo una 'b' e sopravvivo -- ricordate che una macchina a stati finiti esiste solo
  79. se c'è un qualunque percorso sino alla fine -- significa che dovrei essere nello stato tre,
  80. dal quale posso solo passare al quattro.
  81. Al contrario, se fossi ancora qui e vedessi una 'c' ,
  82. potrei essere allo stato quattro, e quindi vado al cinque.
  83. Infine, se sono allo stato quattro e vedo una 'c' ,
  84. finisco con l'essere qui; quindi questa macchina deterministica accetta
  85. lo stesso linguaggio di quella non-deterministica.
  86. Le due stringhe 'abc' e 'ac'
  87. ci sono entrambe, ma non ci sono
  88. epsilon transizioni né ambiguità.
  89. In ogni nodo, non ci sono mai due vertici uscenti con 'a' ,
  90. e neanche epsilon transizioni.
  91. Vediamo un altro esempio di come funziona.
  92. Ancora, mi appresto a costruire una macchina deterministica a a stati finiti
  93. dove ogni stato della macchina deterministica
  94. corrisponde ad un insieme di stati
  95. in quella non-deterministica.
  96. Ancora, riformulando, abbiamo una macchina non-deterministica e
  97. ne costruiremo una deterministica 'D'
  98. che accetta lo stesso linguaggio. Comincerò facendo
  99. corrispondere ad ogni stato in 'D' un insieme di stati
  100. della macchina non-deterministica che avevo all'inizio.