Portuguese, Brazilian subtitles

← 01-58 Nondet To Det

01-58 Não Det para Det

Get Embed Code
4 Languages

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

  1. Vamos praticar mais uma vez.
  2. a conversão de autômato finito não determinista para um determinista.
  3. Desenhei aqui um autômato finito não determinista.
  4. Ele tem ambiguidade.
  5. Aqui, no estado 1, exsitem duas maneiras de ler `a'.
  6. Ele tem também transições epsilon.
  7. Vou começa a desenhar seu equivalente determinista aqui.
  8. Quando entramos no autômato não determinista,
  9. apenas podemos estar no estado 1. Mas, então podemos ver um `a',
  10. e nesse caso podemos ir para 2, 4,
  11. ou tomar a transição epsilon para 5,
  12. ou ainda prosseguir por esta transição epsilon para 6.
  13. Vou então chamar meu novo estado de 2456,
  14. porque ele representa todos os estados para onde posso ir,
  15. se eu estiver simulando este autômato não determinista.
  16. Este estado deveria ser de aceitação, ou não?
  17. Bem, lembre-se que um autômato dinito aceita, se existe ALGUM caminho
  18. para um estado de aceitação, e 6 é um estado de aceitação.
  19. Como o autômato original aceita -- `a',
  20. `a', epsilon, epsilon, ok -- nosso novo autômato também aceita -- `a',
  21. `a', ok.
  22. No meu mundo convertido, um estado é de aceitação se algum dos seus correspondentes
  23. estados originais é de aceitação.
  24. Digamos que eu esteja em 2456, e vejo `c'.
  25. Se estou em 2 e vejo `c', falho.
  26. Se estou em 4 e vejo `c', falho.
  27. De 5, vou para 6 -- ok.
  28. De 6, falho também.
  29. Então aqui, se estou em 2456, e vejo `c',
  30. ou apenas para o estado 6, e este é um estado de aceitação.
  31. Existem outras maneiras de sair de 2456,
  32. e quando fazemos isso, podemos ir para os estados 2 ou 3.
  33. Como 3 é um estado de aceitação,
  34. 23 é um estado de aceitação.
  35. Se eu estou em 23 e vejo `b', de 2 vou para 3,
  36. e de 3 falho. Portanto terminamos neste estado 3.
  37. Se estou em 2 ou 3 e vejo `c',
  38. então eu deveria estar no estado 3, e permaneço no estado 3.
  39. Portanto, tanto com `b', como com `c', vou para o estado 3,
  40. que é também um estado de aceitação.
  41. E se eu estou no estado 3, há um loop aqui, de volta para 3.
  42. Agora já quase fiz quase tudo deste determinista equivalente,
  43. mas me esqueci de rotular um arco.
  44. Então me ajude aqui.
  45. Como exercício, como você deve rotular este arco,
  46. de modo que este autômato determinista e este outro não determinista
  47. aceitem exatamente a mesma linguagem?