Last Update: 30 March 2009
Note: or material is highlighted |
Recursive Case:
Compare building blocks (e.g., Legos):
* The recursive case tells you how to make more of something if you
already have some.
* The base case tells you how to get some in the first place.
(In fact, it gives it to you for free.)
E.g., Let Σ = {a, b, c, …, z}
Then Σ* = {s | s is a string "spelled" with letters from Σ}
= {λ, a, b, …, z, aa, bb, …, zz, …,
abc, …, cat, dog, chat, chien, gato, perro, …
ewiucjmgvjrjhtugvhshcuej, …}
We might even have a set of spelling rules that tell us
which these are. So, "spelled" would be in the set, but
"speled" probably wouldn't be.
Would "lurf" be in the set?
(It's pronounceable, but not a real word (so far).)
Would
"lrxf" be in the set? (It's not even pronounceable, so it
couldn't be a real word.)
If we have a meaning function (called a "semantic interpretation function")
then these two words would have different meanings.
(In English, "chat" means "talk"; in French, it means "cat".)
—then strings are sentences consisting of those words, possibly separated by spaces and possibly with punctuation.
We could also have a "grammar" that tells us which sentences
are grammatically correct (like "this sentence is grammatically
correct")
and which ones aren't (like "this sentence
grammatically incorrect").
This is how we can mathematically (and computationally!) model languages.