Portuguese, Brazilian subtitles

← 01-52 Epsilon And Ambiguity

01-52 Epsilon e Ambiguidade

Get Embed Code
5 Languages

Subtitles translated from English Showing Revision 1 created 12/05/2012 by Lucilia Figueiredo.

  1. O módulo de expressões regulares de Python
  2. usa, de fato, algo bastante similar ao fsmsim, internamente.
  3. Ele pega uma expressão regular
  4. e a transforma esta em um FSM -- esta transformação você fez, num sentido e no outro,
  5. muitas vezes -- e então ele verifica, com um procedimento recursivo simples,
  6. se o FSM aceita o string.
  7. Entretanto, nossa simulação não trata transições epsilon, ou ambiguidade.
  8. O que eu quero dizer com ambiguidade é: o que acontece se existem 2 arcos saindo do estado, com rótulo `a' ?
  9. Digamos que um deles leva a um estado de aceitação, e o outro não.
  10. O que devemos fazer?
  11. Bem, existe uma definição formal para esse tipo de ambiguidade.
  12. Entretanto, isso não vai resolver nossos problemas.
  13. A idéia é que um FSM aceita um string s,
  14. se existe pelo menos um caminho, do estado inicial
  15. a algum estado de aceitação, rotulado com s.
  16. Este FSM aceita `a'
  17. porque existe um caminho para isso, onde `a' nos leva
  18. até um estado de aceitação.
  19. Se você quiser, pode dizer que FSMs são generosas:
  20. se existe uma maneira de aceitar, então aceitamos.
  21. Entretanto, nosso similador de FSM
  22. não codifica esta idéia. Então, vamos ter que retornar
  23. a estas questões.