Motivation:

Materials:

1. Overhead showing word generator for the language of planet ABBA.
2. Currency grammar overhead.
3. One set of sentence-generating materials for each small group of students.
4. Overhead transparency showing the grammar. 

Lesson Plan:

1. Discussion: Some people who work in the field of Artificial Intelligence are primarily interested in "natural language processing." One mechanism they use for generating and recognizing English sentences is the context-free grammar. You may say, "wait! this is a computer science class, not an English class!" But it turns out that these grammars are a particularly useful tool for interpreting computer programming languages, which have a much more limited and more easily defined structure than spoken languages...except on the planet ABBA! 
2. It just so happens that we can describe all the words used on the planet ABBA using a simple word generator called a context free grammar, or just grammar for short.  (Context free grammars, like Boolean circuits and finite state machines, can be used to represent lots of different things besides just alien words. We'll see more examples.) 
3. Place the ABBA handout on the overhead and use it to describe the parts of the grammar.  There are two types of symbols which we call terminals and non-terminals (we happen to use lower case letters for terminals and capital letters for non-terminals). One of the non-terminals is also chosen as a special start symbol (in our first grammar, this is denoted by "S"). In the ABBA language, all words are made up of the letters "a" and "b."  These are the terminals for the ABBA grammar.  Each line of the grammar is a "substitution rule" which allows the non-terminal on the left to be replaced by the sequence of characters on the right which can be any combination of terminals and non-terminals.   The goal is to begin with the start symbol, and repeatedly apply substitution rules until all that remains are terminals. 

Here is the grammar as it appears on the ABBA handout.  

Start symbol: S 

Non-terminals:  S 

Terminals: a, b 

Rules: 

     S -> aSa

     S -> bSb

     S -> a

     S -> b

     S -> aa

     S -> bb

Show 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.

4. Next we'll talk about something we're all familiar with which can be generated using a simple grammar. MONEY!!! Place Currency worksheet on overhead and work through the discussion.
5. Game: Silly Sentences. Now we'll use a grammar to generate English sentences.  You will have to demonstrate how this works. Make sure the sentence grammar is visible to all the students on the overhead. Start by placing the word SENTENCE at the top of your piece of paper (or overhead or chalkboard). SENTENCE is followed by NOUN PHRASE and VERB PHRASE, neither of which is a terminal, so both must be expanded. (Tell the students that the terminals are the symbols that are not circled.) 

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. 

6. Let the students come up with their own silly sentences. They may want to make up their own word cards. They can also use dice to choose which rule to apply when they have a choice (for example, when they are expanding a NOUN PHRASE). 
7. Have some of the students read their sentences aloud. 
8. Challenge the students to think of a sentence which cannot be generated using our grammar. This should be easy. Can they think a sentence which can't be generated by our grammar, but which uses our words? 

Conclusion:

Evaluation:

Extensions:

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. 

Standards:

• NCTM K-4: 1, 2, 3, 4, 13.
• NCTM 5-8: 1, 2, 3, 4, 8.
• NCTM 9-12: 1, 2, 3, 4, 12.

Skills:

• Problem solving / reasoning / communication / connections
• Pattern recognition
• Language arts