## 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
• 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:

more » « less
Video Language:
English
Team:
Udacity
Project:
CS101 - Intro to Computer Science
Duration:
02:28
 Udacity Robot edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science Udacity Robot edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science Udacity Robot edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science Udacity Robot edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science Udacity Robot edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science Udacity Robot edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science Cogi-Admin edited English subtitles for Expanding Our Grammar Solution - Intro to Computer Science

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API