Return to Video

cs262_unit1_32_q_nondet-to-det

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

domanda da non-deterministico a deterministico

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:32
lorenz.mh added a translation

Italian subtitles

Revisions