Return to Video

cs262_unit1_31_l_nondeterminism

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

dummy description

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS262 - Programming Languages
Duration:
05:05
lorenz.mh hozzáadott egy fordítást

Italian subtitles

Felülvizsgálatok