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.


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. 


  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. 
  4. Here is the grammar as it appears on the ABBA handout.  

    Start symbol: S 

    Non-terminals:  S 

    Terminals: a, b 


         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.

  5. 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.
  6. 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.) 
  7. 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. 

  8. 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). 
  9. Have some of the students read their sentences aloud. 
  10. 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? 


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. 


Just observe and encourage participation. 


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. 


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


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

Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt. This lesson and supporting materials may be copied for nonprofit educational use only.