Portuguese, Brazilian subtitles

← 07-13 Super Hard Quiz Of Doom Solution

07-13 Teste Muito Difícil - Solução

Get Embed Code
3 Languages

Subtitles translated from English Showing Revision 1 created 02/27/2013 by Lucilia Figueiredo.

  1. Bem, vamos tentar raciocinar sobre isso, já que é um pouco complicado.
  2. Suponha que você me dá seu autômato de estados finitos A.
  3. Eu desenhei aqui estes ... para indiar que ele poderia ser maior, com outros estados no meio --
  4. eu não sei o que é isso, isso pode representar qualquer autômato de estados finito.
  5. Mas eu sei que ele tem um estado inicial e um estado final.
  6. Aqui, o que eu vou fazer é: eu vou desenhar uma outra cópia de A no meu papel.
  7. Então, eu volto no meu primeiro autômato e, onde isto era um estado final,
  8. eu faço com que ele deixe de ser um estado final -- então eu mudo essa parte.
  9. Então, eu vou adicionar uma trasição ε aqui, e vou apagar essa outra seta que indica que este é um estado inicial.
  10. Agora eu tenho um novo autômato de estados finito, que aceita strings da seguinte forma:
  11. deve haver uma parte -- x -- aqui, que seria aceita por A,
  12. e depois outra parte, possivelmente diferente aqui -- y -- que seria também aceita por A.
  13. Então, em geral, eu aceito x ε y -- ou xy.
  14. De fato, eu sempre posso fazer isso.
  15. Se você me dá qualquer autômato de estados finito A, eu sempre posso construir um autômato de estados finito duas vezes maior,
  16. que aceita um string de A, seguido de outro string, independente, separado, também aceito por A.
  17. Entretanto, este aqui é um pouco mais complicado.
  18. Acontece que a resposta é: algumas vezes.
  19. Deixe-me dar um exemplo de SIM e um exemplo de NÃO.
  20. Digamos que o autômato de estados finito que você me dá como sendo B aceita apenas um string -- b.
  21. Eu vou fazer o mesmo truque de antes. E agora eu tenho um novo autômato de estados finito, que aceita bb.
  22. Como este é o único string da linguagem, eu agora o dupliquei. Isso funciona ok.
  23. Eu posso fazer isso pelo menos em um caso. Mas agora vem a parte ruim.
  24. Para este exemplo de B aqui em cima -- este em azui -- funcionou corretamente.
  25. Mas agora eu vou dar um exemplo de B para o qual isso não funciona.
  26. Aqui, B é a*x.
  27. Este autômato de estados finito aceita a expressão regular a*x --
  28. qualquer número de a's, possivelmente 0, seguido de um x.
  29. Agora, note a diferença entre esta sentença e a anterior.
  30. Isso requer exatamente o mesmo string duplicado.
  31. Vamos imaginar que eu complete essa construção do autômato de estados finito --
  32. o mesmo tipo de coisa que eu fiz antes.
  33. Agora, eu vou escrever alguns strings que podem ser a*x duas vezes.
  34. Bem, eu poderia não ter a's,-- então eu tenho nenhum a, seguido de um x.
  35. Ou eu poderia ter um a -- isso parece ok, por enquanto --
  36. Ou poderia ter dois a's, ou poderia ter três a's.
  37. Esse padrão deveria parecer promissor.
  38. Mas, em geral, se eu pudesse duplicar este autômato de modo que ele aceite o mesmo string nnas duas vezes,
  39. ao invés de um novo string cada vez, eu poderia reconhecer (a^n)x(a^n)x.
  40. Pela mesma razão que (a^n)(b^n) nãopode ser reconhecido -- não é regular -- também isso não pode.
  41. Temos aqui um exemplo positivo e um exemplo negativo.
  42. Portanto isso é verdade algumas vezes.
  43. Isso foi um bem difícil. Não se sinta mal se você não viu isso de primeira.