Return to Video

03xpsps-01 Fsm Optimization Solution

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

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

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
05:24
Lucilia Figueiredo added a translation

Portuguese, Brazilian subtitles

Revisions