Return to Video

01-57 Nondeterminism

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

01-57 Não Determinismo

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS262 - Programming Languages
Duration:
05:05
Lucilia Figueiredo edited Portuguese, Brazilian subtitles for 01-57 Nondeterminism
Lucilia Figueiredo hozzáadott egy fordítást

Portuguese, Brazilian subtitles

Felülvizsgálatok Compare revisions