Portuguese, Brazilian subtitles

← 01-57 Nondeterminism

01-57 Não Determinismo

Get Embed Code
5 Languages

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

  1. Esses FSMs mais fáceis de definir, que agora estamos usando,
  2. que contêm transições epsilon ou ambiguidade --
  3. lembre-se que ambiguidade significa que eu posso ir para dois lugares distintos com a mesma entrada --
  4. são formalmente chamados de autômatos de estados finitos não deterministas.
  5. Não determinismo aqui significa que você pode não saber
  6. para onde ir.
  7. Não é um estado sem saída. Você tem escolhas.
  8. Você tem liberdade.
  9. Um FSM sem transições epsilon
  10. e sem ambiguidade é chamado de autômato de estados finito determinista.
  11. Tudo é determinado, a partir do estado incial.
  12. Dados o autômato de estados finito e a entrada, sempre é possível saber
  13. exatamente o que vai acontecer.
  14. Nosso simulador de FSM é capaz de tratar
  15. autômatos deterministas.
  16. Por isso ele é muito útil para a implementação de expressões regulares
  17. internamente.
  18. Dexe-me mostrar um exemplo deste não determinismo, como ilustração.
  19. Vamos voltar a este FSM aqui,
  20. mas agora e entrada é 1-23.
  21. Onde estamos?
  22. Começamos aqui e, com `1', vamos para cá,
  23. e então, se quero reconhecer um hífen, devo vir para cá, onde há um hífen --
  24. temos que pegar um hífen --
  25. e agora temos um 2, mas agora não é muito óbvio.
  26. Posso ficar aqui, neste loop, com `3',
  27. ou voltar, através desta transição epsilon,
  28. e fazer este loop aqui, com `3'. Então podemos estar no estado 3 ou no 5.
  29. Como não existe uma única resposta sobre onde eu estaria,
  30. isso é não determinista.
  31. Como um comentário à parte, essa noção de determinismo,
  32. ou não determinismo, está relacionada à questão do livre arbítrio, em filosofia.
  33. Podemos de fato fazer escolhas independentes?
  34. Ou tudo é pré-determinado pelo estado corrente do mundo,
  35. e nos força a agir sobre ele, como em um jogo de bilhar ou de poker?
  36. Alguns filósofos abordam essa questão sugerindo que temos
  37. a ilusão de livre arbítrio -- esse é um pensamento desconcertante --
  38. que é adequado para descrever experiência subjetiva.
  39. Certamente temos a sensação de ter livre arbítrio,
  40. independentemente do que acontece no mundo,
  41. Algo similar ocorre com
  42. autômatos de estados finitos.
  43. Embora autômatos de estados finitos deterministas pareçam ter
  44. muito mais poder e muito mais liberdade,
  45. qualquer coisa que pode ser feita com eles também pode ser feita
  46. em nosso mundo determinista do jogo de bilhar.
  47. De fato, você vai ver que posso mostrar isso agora mesmo.
  48. Todo autômato finito não determinista
  49. tem um autômato finito determinista correspondente,
  50. que aceita exatamente os mesmos strings.
  51. Autômatos finitos não detemrinistas não são mais poderosos
  52. do que autômatos finitios deterministas.
  53. Eles são apenas mais convenientes.
  54. É mais fácil projetá-los.
  55. Vejamos um exemplo disso.
  56. Suponha que temos esta expressão regular.
  57. Existem apenas 2 strings na linguagem desta expressão regular.
  58. Desenhamos aqui um FSM bastante elaborado para esta expressão,
  59. que tem várias transições epsilon.
  60. Ele é bastante não determinista.
  61. Nós queremos reconhecer um `a', mas estas 2 transições epsilon aqui
  62. representam uma escolha.
  63. Escolho esta, com `b', ou pulo por aqui ?
  64. Na rota de cima, temos que ver um `b'.
  65. Na rota inferior, o ignoramos completamente.
  66. E em qualquer caso eu preciso ver um `c'.
  67. Vou desenhar agora um autômato determinista
  68. que faz exatamente a mesma coisa. E vou dar uma dica
  69. de como essa conversão funciona.
  70. Veremos isso novamente daqui a pouco.
  71. Depois de ver um `a', eu posso estar em 2
  72. ou posso tomar a transição epsilon para 3.
  73. Eu poderia também tomar a transição epsilon para 6,
  74. ou ainda prosseguir para 4. Existem portanto três possíveis
  75. lugares onde eu poderia estar.
  76. Um bocado de lugares.
  77. Vou simplesmente registrar todos eles como um novo estado 2364.
  78. Daqui, se eu vejo um `b' e sobrevivo -- lembre-se que um FSM
  79. continua se existir algum caminho que o leva até o final -- eu só poderia ter ido para o estado 3,
  80. e dai para o estado 4.
  81. Por outro lado, se eu estou aqui, e vejo um `c',
  82. então eu só poderia ter ido para o estado 4 e daí vou para o 5.
  83. Então, finalmente, se estou no estado 4, e vejo um `c',
  84. eu termino aqui. Portanto, este autômato determinista
  85. aceita a mesma linguagem que este aqui acima.
  86. Os dois strings `abc` e `ac`
  87. são ambos aceitos, mas este FSM
  88. não tem transições epsilon ou ambiguidade.
  89. De nenhum estado existem 2 arcos saindo, com rótulo `a'
  90. e também não há transições epsilon.
  91. Vejamos um outro exemplo de como isso funciona.
  92. Novamente, vou construir um autômato determinista,
  93. tal que cada estado desse autômato determinista
  94. corresponde a um conjunto de estados
  95. do autômato não determinista.
  96. Em outras palavras, se você me dá um autômato finito não determinista,
  97. eu posso construir uma autômato determinista D
  98. que aceita a mesma linguagem. A maneira de fazer isso é
  99. que cada estado em D corresponde a um conjunto de estados
  100. do autômato não determinista que você me deu.