|Lesson 6: Grammars|
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit
educational use only.
Motivation:Grammars for English and other natural languages govern how words may be combined to form proper sentences. In computer science an analogous notion of "formal grammar" has proved to be very useful in describing programming languages, and in understanding the meaning of a given program. In this lesson we will examine the basic ideas behind a type of formal grammar called a Context Free Grammar. These grammars are a somewhat different notion than our common idea of a language grammar, though they can be used to generate a small subset of English sentences.
Here is the grammar as it appears on the ABBA handout.
Start symbol: S
Terminals: a, b
S -> aSa S -> bSb S -> a S -> b S -> aa S -> bbShow your students how to use this grammar to generate the word "abbba", by starting with S, the start symbol, then applying the first rule and replacing S with aSa, then applying the 2nd rule replacing aSa with abSba, and finally using the 4th rule to replace the S in abSba with the letter b. Ask them what other sequences they can generate. Let them generate a few and "read" the words! What do all these sequences have in common? Answer: all and only those that read the same forwards and backwards (called palindromes). Can they explain how the grammar works?
If this part of the lesson seems too hard, start instead with a simpler grammar such as: S -> aS, S -> a, which generates strings of any number of a's. A slightly harder one is: S -> aaS, S -> aa, which generates strings with an even number of a's.
Note that NOUN PHRASE has two options. Choose one of the options (it doesn't matter which), and substitute for NOUN PHRASE accordingly. Then expand VERB PHRASE. Continue this process until all non-terminals are replaced by terminals. Finally, replace each terminal part of speech with a word card of the same color.
Conclusion:Students may be familiar with the parts of speech such as nouns, verbs, etc., but may not realize that it is possible to capture (to some extent) the underlying structure of sentences. Grammars are useful devices for describing structure of natural spoken languages, as well as programming languages. They also prove useful in modeling structural properties of other systems.
Evaluation:Just observe and encourage participation.
Extensions:Another interesting exercise is to ask the students to write a sentence and check whether or not it follows the rules of the grammar. The students can be asked to come up with a scheme for checking. (In general the way to do this is to use the grammar in reverse until you arrive at a single non-terminal.) This process is called "parsing" a sentence.
There is a machine which recognizes Context Free Languages called a Push Down Automaton (PDA for short). Have the students investigate this machine.
Improve upon the English grammar. (This can be viewed as a research task since there are many references. Try looking on the web.)
Investigate sequences and languages which cannot be generated using context-free grammars.
Investigate grammars and structures of other items besides text.
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt. This lesson and supporting materials may be copied for nonprofit educational use only.