Return to Video

cs262_unit1_28_l_epsilon-and-ambiguity

  • 0:00 - 0:03
    Scopriamo che il modulo Python per le espressioni regolari
  • 0:03 - 0:07
    usa un meccanismo abbastanza simile al nostro simulatore.
  • 0:07 - 0:09
    Prende l'espressione regolare,
  • 0:09 - 0:12
    la trasforma in una macchina a stati finiti, come avete avuto modo provare in entrambi i sensi
  • 0:12 - 0:17
    più volte, e poi la controlla con una semplice procedura ricorsiva
  • 0:17 - 0:20
    per vedere se la macchina accetta la stringa.
  • 0:20 - 0:25
    Purtroppo, il nostro simulatore non supporta transizioni epsilon o ambiguità,
  • 0:25 - 0:29
    cosa succede se ci sono due vertici uscenti entrambi etichettati con 'a' ?
  • 0:29 - 0:32
    Diciamo che uno conduca ad uno stato accettante, e l'altro no.
  • 0:32 - 0:34
    Cosa dovremmo fare?
  • 0:34 - 0:36
    Bhé, c'è una definizione formale per questo tipo di ambiguità.
  • 0:36 - 0:38
    Che non risolverà il nostro problema però.
  • 0:38 - 0:41
    Vediamo come una macchina a stati finiti accetta una stringa 's'
  • 0:41 - 0:46
    se esiste almeno un percorso dallo stato iniziale
  • 0:46 - 0:49
    ad un qualsiasi stato accettante che segue 's' .
  • 0:49 - 0:52
    Questa macchina accetta 'a'
  • 0:52 - 0:55
    poiché c'è un percorso per farlo che
  • 0:55 - 0:57
    conduce ad uno stato accettante.
  • 0:57 - 1:00
    Se preferite, potete dire che le macchine a stati finiti sono generose.
  • 1:00 - 1:03
    Se c'è anche una sola via per accettare, la utilizzeremo.
  • 1:03 - 1:06
    Purtroppo, la nostra simulazione di macchina a stati finiti
  • 1:06 - 1:08
    non gestisce questa situazione, quindi dovremo tornarci
  • 1:08 -
    per risolvere entrambi questi problemi.
Title:
cs262_unit1_28_l_epsilon-and-ambiguity
Description:

spiegazione epsilon e ambiguità

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

Italian subtitles

Revisions