Return to Video

01-52 Epsilon And Ambiguity

  • 0:00 - 0:03
    O módulo de expressões regulares de Python
  • 0:03 - 0:07
    usa, de fato, algo bastante similar ao fsmsim, internamente.
  • 0:07 - 0:09
    Ele pega uma expressão regular
  • 0:09 - 0:12
    e a transforma esta em um FSM -- esta transformação você fez, num sentido e no outro,
  • 0:12 - 0:17
    muitas vezes -- e então ele verifica, com um procedimento recursivo simples,
  • 0:17 - 0:20
    se o FSM aceita o string.
  • 0:20 - 0:25
    Entretanto, nossa simulação não trata transições epsilon, ou ambiguidade.
  • 0:25 - 0:29
    O que eu quero dizer com ambiguidade é: o que acontece se existem 2 arcos saindo do estado, com rótulo `a' ?
  • 0:29 - 0:32
    Digamos que um deles leva a um estado de aceitação, e o outro não.
  • 0:32 - 0:34
    O que devemos fazer?
  • 0:34 - 0:36
    Bem, existe uma definição formal para esse tipo de ambiguidade.
  • 0:36 - 0:38
    Entretanto, isso não vai resolver nossos problemas.
  • 0:38 - 0:41
    A idéia é que um FSM aceita um string s,
  • 0:41 - 0:46
    se existe pelo menos um caminho, do estado inicial
  • 0:46 - 0:49
    a algum estado de aceitação, rotulado com s.
  • 0:49 - 0:52
    Este FSM aceita `a'
  • 0:52 - 0:55
    porque existe um caminho para isso, onde `a' nos leva
  • 0:55 - 0:57
    até um estado de aceitação.
  • 0:57 - 1:00
    Se você quiser, pode dizer que FSMs são generosas:
  • 1:00 - 1:03
    se existe uma maneira de aceitar, então aceitamos.
  • 1:03 - 1:06
    Entretanto, nosso similador de FSM
  • 1:06 - 1:08
    não codifica esta idéia. Então, vamos ter que retornar
  • 1:08 -
    a estas questões.
Title:
01-52 Epsilon And Ambiguity
Description:

01-52 Epsilon e Ambiguidade

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

Portuguese, Brazilian subtitles

Revisions