Portuguese, Brazilian subtitles

← 01-59 Nondet To Det Solution

01-59 Não Det para Det - Solução

Get Embed Code
4 Languages

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

  1. Vamos achar aqui um lugar para fazer um rascunho.
  2. Exitem 1,2,3 letras: a, b e c envolvidas.
  3. Então, vamos dar uma olhada em cada uma, para ver qual serve.
  4. Suponha que aqui no estado 2456 eu vejo um `a'.
  5. Se estou em 2 e vejo `a', falho; em 4, se vejo `a', falho,
  6. em 5, se vejo `a', falho; em 6, se vejo `a', falho.
  7. Não serve.
  8. 2456 deve falhar.
  9. Não vai para 23.
  10. Muito bem, e se eu vejo um `b'?
  11. Se estou em 2 e vejo `b', vou para 3 -- isso parece ok;
  12. em 4 e vejo `b', falho;
  13. em 5 e vejo `b', vou para 2;
  14. em 6 e vejo `b', falho.
  15. Oh, `b'nos leva exatamente para 2 e 3.
  16. 2456, com `b', vai para 23.
  17. Mas vamos terminar de verificar com `c', par o caso de estarmos esquecendo algo.
  18. Estou em 2456.
  19. de 2, com `c', não vou a lugar nenhum;
  20. de 4, com `c', não vou a lugar nengum;
  21. de 5, com `c', vou para 6;
  22. e de 6, com `c', não vou a lugar nenhum. Então de 2456,
  23. com `c', vou para 6.
  24. De fato, já temos esse arco: 2456, com `c', vai para 6.
  25. Como este autômato é determinista, queremos apenas um arco
  26. saindo daqui, com rótulo `c'.
  27. Parece que `b' é o vencedor.
  28. O rótulo deste arco é `b'.
  29. Bem, isto não é uma prova,
  30. mas pode-se provar que qualquer autômato não determinista
  31. pode ser convertido em um determinista equivalente,
  32. usando exatamente esses passo.