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

1. Title:
   07-20 Learning Regular Expressions Solution
2. Description:

   Other units in this course below:
   Unit 1:http://www.youtube.com/playlist?list=PL3FEF9299137945CC
   Unit 2:http://www.youtube.com/playlist?list=PLBF6FC32358457242
   Unit 3:http://www.youtube.com/playlist?list=PL30EF9EB86B4D2E54
   Unit 4:http://www.youtube.com/playlist?list=PL6881C8D2E9D63242
   Unit 5:http://www.youtube.com/playlist?list=PL62AF1F6D3B654E14
   Unit 6:http://www.youtube.com/playlist?list=PL8FCC9D9C45A6640E
   Unit 7:http://www.youtube.com/playlist?list=PL9533BCB71FD88E38

   Q&A: http://www.youtube.com/playlist?list=PLE0EB375FA373A866

   To gain access to interactive quizzes, homework, programming assignments and a helpful community, join the class at http://www.udacity.com

3. 0 0:00 - 0:02
   Well, there are a number of ways to go about this--
4. 2000 0:02 - 0:05
   actually, an infinite number of ways to go about this.
5. 5000 0:05 - 0:09
   An entirely legitimate strategy but one that might feel almost like cheating
6. 9000 0:09 - 0:11
   would be just to put these together.
7. 11000 0:11 - 0:16
   You could submit the Python code that corresponds to either this or this or this.
8. 16000 0:16 - 0:20
   Now you're guaranteed that it accepts the three strings on the left and nothing else.
9. 20000 0:20 - 0:23
   Now, you'd have to be careful about how you group things or whatnot,
10. 23000 0:23 - 0:27
    so that the or and the parentheses would bind correctly, but that's one way to do it.
11. 27000 0:27 - 0:32
    Let's go see if we can make a more natural feeling regular expression that actually does it though.
12. 32000 0:32 - 0:34
    It looks like we definitely have to start with an a.
13. 34000 0:34 - 0:39
    Now I have my choice of what I want to say the difference is between these other strings--
14. 39000 0:39 - 0:42
    abb and here we've got aabbb.
15. 42000 0:42 - 0:46
    In some sense one of the key differences is the number of b's.
16. 46000 0:46 - 0:51
    Here's one regular expression that captures all the ones on the left and none of the ones on the right.
17. 51000 0:51 - 0:56
    It's an a*--so that gets this first one, and then after you're done with the a's,
18. 56000 0:56 - 1:01
    you may optionally have either bb or cc. Great.
19. 61000 1:01 - 1:04
    That gets 1, 2, and 3 but none of these to hers.
20. 64000 1:04 - 1:08
    This one is ruled because it's not bb cc with a's in front of it.
21. 68000 1:08 - 1:10
    These have too many b's. These have too many c's.
22. 70000 1:10 - 1:13
    But there are a large number of ways you could've done this.
23. 73000 1:13 - 1:19
    In fact, there is an area of study called learning theory that tries to make machines find patterns
24. 79000 1:19 - 1:21
    the same way that we can with our brain.
25. 81000 1:21 - 1:27
    There's a notion that you've really learned something when you've abstracted it to a small rule.
26. 87000 1:27 - 1:32
    The reason we're less happy with this answer up here is because its' over-fitting the data in some sense.
27. 92000 1:32 - 1:36
    It's just recording the yes instances. It's not really generalizing the pattern.
28. 96000 1:36 - 1:41
    We say that more learning is happening when we generalize a smaller pattern
29. 101000 1:41 -
    than just copying all of the available input, but that was by no means required for this problem.