Skip to content

Lab 4

The exercises for this week are available below for download as a PDF file.

Download Exercises File

  • Exercises 1--2 are to familiarise you with the "minimum pumping length". How you compute it for RLs, and what it really means.

  • You then have a few PL Games to play in exercises 3--7. These are not necessarily in increasing order of challenge.

  • JFLAP offers a cut-down version of the game where you can try the game out for concrete values of the pumping length \(p\). (But they call it \(m\).) It is however important to understand that, for non-RLs, you cannot just pick a fixed value for \(p\) and win the game. You must win whatever the value of \(p\) is.

  • Some more challenging languages are given in the orange section in increasing order of challenge.


In advance of your lab session, you need to:

  1. Refresh your knowledge of the key concepts covered in the lecture videos.
  2. Attempt to solve the green exercises.
  3. Then attempt the orange exercises.
  4. Highlight any challenging exercises to ask about them during your lab sessions.
  5. If you want to attempt the advanced/optional (red/blue) exercises then do so.