YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Portuguese, Brazilian subtitles

← 03xpsps-01 Fsm Optimization Solution

03xpsps-01 Otimização de FSM - Solução

Get Embed Code
3 Languages

Subtitles translated from English Showing Revision 1 created 01/15/2013 by Lucilia Figueiredo.

  1. Neste problema, temos um desafio, e por isso eu o marquei
  2. com duas estrelas. O que queremos fazer aqui
  3. é otimizar um atômato de estados finito.
  4. Vejamos um exemplo. Suponha que temos este autômato de estados finito.
  5. Ele tem um estado de aceitação -- estado 1 -- e temos estes outros estados.
  6. Se você olhar rapidamente e pensar um pouco,
  7. verá que uma vez que tomamos o caminho com 'b' para o estado 2,
  8. nunca podemos chegar a um estado de aceitação.
  9. Do estado 2, 3, ou 4, não há como chegar ao estado 1.
  10. Portanto, qualquer string que leve a este camoinho sempre irá falhar.
  11. Este autômato é equivalente a este outro, que não inclui estes estados.
  12. Portanto, podemos tornálo muito mais simples.
  13. Porque desejamos fazer isso?
  14. Bem, se você ainda não notou, temos usado muito expressões regulares,
  15. para construir nosso web browser.
  16. Essas expressões regulares são representadas como autômatos de estados finitos,
  17. e é assim que são processadas.
  18. Para tornar nosso web browser mais rápido, queremos autômatos de estados finitos tão simples
  19. quanto possível.
  20. Então, vamos escrever um código para,
  21. dada uma definição de um autômato de estados finito, tal como este aqui,
  22. identificar estado que não são releventes para a execução,
  23. que vamos chamar de estados mortos, e removê-los da definição,
  24. mantendo exatamente a mesma linguagem - reconhecendo exatamente os mesmo strings. --
  25. que o nosso autômato de estados finito original.
  26. Como vamos fazer isso? Vamos traçar um plano.
  27. Aqui está 'O Plano'.
  28. Passo 1: vamos encontrar os estado vivos e os estados mortos.
  29. Vamos fazer isso simplesmente encontrando os estados vivos e supondo que todos os demais são mortos.
  30. Como vamos então fazer isso?
  31. Bem, vamos encontrar todos os estados, e podemos fazer isso iterando sobre o nosso dicionário,
  32. Para cada estado, vamos executar nfsmaccepts --
  33. que codificamos no exercício 1 e que é uma função que, dada uma definição
  34. de um atômato finito, um estado inicial, e os estado de aceitação,
  35. verifica se é possível chegar desse estado até um estado de aceitação --
  36. se é possível ter sucesso a partir de onde estamos.
  37. Portnto, se eu dou esta definição e o estado 3, a função vai retornar que não, não posso chegar ao estado 1,
  38. ou a qualquer outro estado de aceitação.
  39. Se eu dou como entrada 1, a função retorna sim, ok.
  40. Então, esta será nossa definição de vivo versus morto.
  41. Eu realmente posso dizer se um estado é vivo ou morto -- isso é ótimo!
  42. Passo 2: Criar um novo autômato finito, que não tenha
  43. nenhum estado morto.
  44. Para obter uma definição realmente boa, bem limpa, é necessário ter um certo cuidado.
  45. Não queremos incluir transições que levem a um estado morto.
  46. Queremos remover todos os estados mortos,
  47. e também queremos remover estado que não apontam mais para nenhum estado vivo.
  48. Então, aqui, temos algumas pequenas subpartes.
  49. Vamos percorrer cada arco do grafo -- cada entrada do dicionário.
  50. Se o estado de origem for morto, não vamos copiá-lo no nosso novo autômato.
  51. Caso contrário, vamos percorrer cada um dos estados de destino,
  52. no nosso autômato original, e nos preparar para copiar todos aqueles que ainda permanecem vivos.
  53. Se não existir nenhum ainda vivo, vamos remover o arco completamente --
  54. não vamos copiá-lo para o autômato novo.
  55. Uma vez que tenhamos repetido esse processo para cada arco do grafo,
  56. vamos atualizar nossa lista de estados de acitação, de maneira correspondente:
  57. Não queremos nenhum estado de aceitação que seja morto.
  58. Vamos então à solução.
  59. A primeira coisa que eu fiz foi copiar nsfmaccepts,
  60. diretamente do exercício da unidade 1,
  61. sem modificar nada.
  62. Agora vou simplificar meu autômato de estados finito.
  63. Como eu disse antes, vou ter que encontrar todos os estados,
  64. de modo que eu tenha uma lista com todos eles, e não importa se eles ocorrem duplicados na lista.
  65. Isso pode tornar minha simplificação um pouco mais lenta, mas eu estou fazendo assim para ecomizar tempo
  66. na execução, mesmo que não na simplificação.
  67. Para cada estado, se ele for vivo -- eu posso determinar isso usando nfsmaccepts --
  68. se ele for vivo vou adicioná-lo à lista de estados vivos.
  69. Agora vou criar um novo dicionário de arcos -- minha nova representação --
  70. e vou percorrer todos os arcos antigos, para ver se eles envolvem apenas estados vivos, e atualizá-lo de modo apropriado.
  71. Então, para cada arco do dicionário, se o estado de origem é vivo,
  72. vou calcular a nova lista de estados de destino, o que significa que vou remover os destinos
  73. que agora estão mortos --
  74. então, se o destino é vivo, vou inclui-lo na lista.
  75. Mas eu apenas quero incluir este arco no dicionário do meu novo autômato finito
  76. se a lista de destinos for não vazia --
  77. não faz sentido incluir um arco que não vai para lugar nenhum,
  78. pois isso significa falha.
  79. É como se supusermos sempre que, se um arco não existe, então temos uma falha.
  80. Finalmente, quero atualizar minha lista de estados de aceitação, de modo que inclua apenas estados vivos.
  81. Vou retornar a tupla com os novos arcos e os novos estados de aceitação.
  82. E é isso.
  83. Veja! É True! É mesmo True!
  84. True significa correto. Significa ótimo.