Return to Video

01-58 Nondet To Det

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

01-58 Não Det para Det

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

Portuguese, Brazilian subtitles

Revisions