English subtitles

← 07-13 Super Hard Quiz Of Doom Solution

Get Embed Code
3 Languages

Showing Revision 1 created 06/29/2012 by Amara Bot.

  1. Well, let's try to reason these out since they're extra complicated.
  2. Suppose you give me your finite state machine A.
  3. Here I've drawn all these dots to mean it could be bigger in the middle.
  4. I don't get to know what it is. This is going to have to work for any finite state machine.
  5. But I do know that it has a start state and an end state--a final state.
  6. Here's what I'm going to do. I'm going to draw another copy of A on my paper.
  7. Then I'm going to go back to the first one and where it was a final state,
  8. I'm going to make it not a final state, so I change this part.
  9. Then I'm going to add an epsilon transition here, and I'm going to erase this other start state arrow.
  10. Now I have a new finite state machine that accepts strings of the following form--
  11. there has to be some part x here that would've been accepted by A.
  12. Then there's some possibly different part y here that would be accepted by A again,
  13. so in general I accept x epsilon y or just xy.
  14. In fact, I can always do this.
  15. If you give me any finite state machine, I can always make a twice as big finite state machine
  16. that accepts one string from you followed by one independent, separate string from you.
  17. However, for this one it's going to be a little more complicated.
  18. It turns out that the answer is only sometimes.
  19. Let me give you an example for yes and an example for no.
  20. Let's say the finite state machine you give me for big B just has one string in it--lowercase b.
  21. I'll do the same trickery as before, and now I have a new finite state machine that accepts bb.
  22. Since there is only one string in the language, I've now doubled it. This works fine.
  23. I can do it at least once, but now here comes the evil part.
  24. This upper example--this blue example--of B totally worked.
  25. Now I'm going give you an example for B that does not.
  26. Here, B is a*x.
  27. This finite state machine accepts the regular expression a*x.
  28. Any number of a's, possibly zero, but then you need an x.
  29. Now, note the difference between this sentence and its earlier copy.
  30. This requires exactly the same string double.
  31. Let's imagine that I do complete this finite state machine construction--
  32. the same sort of thing I've done before.
  33. Now I'm going to write out some of the strings that would be in a*x twice.
  34. Well, I could have no a's, so then I have no a's followed by an x.
  35. Or I could have one a--that's looking okay so far.
  36. Or I could have two a's, or I could have three a's.
  37. This pattern should be looking ominous.
  38. Or in general, if I were able to double this machine so that it accepted the same string both times
  39. rather than a new string each time, I would be recognizing (a^n)x(a^n)x.
  40. For the same reason that a^Nb^n can't be recognized--it's not regular--neither can this.
  41. Here we have one positive example and one negative example,
  42. so it only holds sometimes.
  43. This was super tricky. Do not feel bad if you didn't see this the first time.