Return to Video

Expanding Our Grammar Solution - Intro to Computer Science

  • 0:00 - 0:04
    So now, the answer is infinitely many. All we needed
  • 0:04 - 0:07
    was these two rules and we can make infinitely many words.
  • 0:07 - 0:11
    This is the power that recursive definitions give us. And unlike
  • 0:11 - 0:13
    the previous definition which was circular, what we have now is
  • 0:13 - 0:16
    what we call a recursive definition. That means, we have
  • 0:16 - 0:19
    defined word in terms of itself but that's not the only
  • 0:19 - 0:23
    way we've defined word. We also have this other rule that
  • 0:23 - 0:25
    allows us to have a starting point. That there's one word
  • 0:25 - 0:30
    that we have that's defined not in terms of itself. So here's how we can
  • 0:30 - 0:33
    make infinitely many words using these rules. So
  • 0:33 - 0:37
    we can start with a non-terminal word and
  • 0:37 - 0:43
    let's say we choose to use the first rule. We can replace word directly with
  • 0:43 - 0:46
    our [UNKNOWN] and we're done, but we have
  • 0:46 - 0:50
    another option. We could have replaced word using
  • 0:50 - 0:58
    the second rule, with counter word and if we replace this word, using the
  • 0:58 - 1:00
    second rule, we'll end with that word
  • 1:00 - 1:04
    counter hippo [UNKNOWN] phobia. But that's not the
  • 1:04 - 1:08
    only choice, right, we could've chosen to use the first rule again, and then we
  • 1:08 - 1:11
    were to replace this word with counter-word
  • 1:11 - 1:15
    and so now we have counter, counter, word.
  • 1:15 - 1:17
    Again we have the choice of what to do with this word.
  • 1:19 - 1:24
    We could use the second rule, replace it with the terminal. And
  • 1:24 - 1:28
    then we'll have counter, counter hippo. Or we could replace it using
  • 1:28 - 1:32
    the first rule. And then we'll have counter, counter, counter followed by word.
  • 1:35 - 1:38
    So this can keep going as long as we want.
  • 1:38 - 1:40
    We can produce all of these words with any number of
  • 1:40 - 1:44
    counter, either zero, repetitions of counter one, two, three, four. As
  • 1:44 - 1:47
    many as we want. That means we can produce infinitely many
  • 1:47 - 1:50
    words. Some of them are going to be pretty hard to pronounce.
  • 1:50 - 1:53
    Actually, they're all pretty hard to pronounce. But, there's no limit
  • 1:53 - 1:56
    to the number of words that we can produce this way.
  • 1:56 - 2:00
    So this is what's called the recursive definition and the important
  • 2:00 - 2:05
    thing that it has is two parts. It has a base case which is here.
  • 2:07 - 2:10
    That's the stopping condition. That's something that says
  • 2:10 - 2:12
    we have at least one word that we
  • 2:12 - 2:17
    can define already. That we don't need to define in terms of word. And it has
  • 2:17 - 2:23
    the recursive case that says we can define a word in terms of another word. And
  • 2:23 - 2:25
    if we combine those two, well now we
  • 2:25 - 2:27
    have a definition that can make infinitely many words.
Title:
Expanding Our Grammar Solution - Intro to Computer Science
Description:

22-08 Expanding Our Grammar Solution

more » « less
Video Language:
English
Team:
Udacity
Project:
CS101 - Intro to Computer Science
Duration:
02:28

English subtitles

Revisions Compare revisions