In this activity, the students practice four proofs that demonstrate Pumping lemma. The first proof is almost fully worked out as an example. With each next proof there is less and less text, and students have to find the solution.
| Parameters: | |
|---|---|
| Duration: | 45 minutes |
| Participants: | 2–20 students |
| Instructors: | 1 teacher |
| Class: | tables |
| Resources: | printed handouts |
| Prerequisites: | read notation of formal languages, ideally knowing Pumping lemma for regular languages |
- Understand Pumping lemma for context-free languages.
- Apply the lemma to prove that several given languages are not context-free.
- Print all the 4 pages of the PDF handout (English or Czech) N/3 times, where N is the total number of students. Use one-sided printing.
- Create groups of three or four students.
- Hand out the page 1 to each group. Let them read it and discuss within groups whether they understand the notation. Be ready to answer questions if a group needs to clarify something.
- Let each group fill out the 3rd case and the pumping for the 4th case. If the students haven't used Pumping lemma before, this phase can take 15 minutes.
- When a group is finished, take the page 1 away and give them page 2. It contains the same language but a different word, for which the 3rd case is more complicated, but it is pumped the same way.
- [Optional step] When they figure it out, ask what would happen if the word was
a^(n/3). They have to find out that this cannot be pumped fori = 0, but it works fori = 2. - Take the page 2 away from the group and give them page 3. It contains a new language and requires the student to think about their own word. It might appear that the same word as on page 1 can be used, but it can't, for the same reason as in step 5. They have to find the word
a^nb^ncb^na^n. - When a group is finished, take the page 3 away and give them page 4. Here, they have to work out the whole proof themselves.
- The groups need not be in sync. They can progress at their own pace, but you have to be ready to answer individual questions.
- Have groups of three to four students. You don't want too many groups, as you need to spend a lot of time with each individually.
- The activity is deliberately structured in a way that it requires progressively more own writing from the students.
- Answer questions before handing out a new page.
- Explanation and example of the Pumping lemma on Wikipedia.
Karel Kubíček, 2016.