Skip to content

Lab 5

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

Download Exercises File

Green section

  • Exercise 1 is a simple task to get you used to how PDAs work, and how to specify them formally.

  • Exercise 2 shows you a number of context-free grammars (CFGs) to help you familiarise yourself with how they work, and how to write string derivations or parse trees.

  • Exercises 3--5 move you to the creative level and asks you to design grammars and/or PDAs for some languages.

    Try to use the "tricks" you have learnt with NFAs such as concatenation and union of languages to simplify your task.

    The new tool that was not available to NFA is the stack. Use this to count. Everytime you see \(n\) you should try to capture it on the stack.

    Another thing you can achieve with a stack is to memorise a pattern and then recall it backwards, as was used for \(ww^R\) in the lecture.

Orange section

  • The orange section introduce you to the concepts of ambiguity, and gives you more languages to design CFGs/PDAs for them.

Todo

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.