Skip to content

Solutions to Lab 6 exercises & Reflection

Written solutions

The written solutions for this week can be download as PDF below.

Download Solutions to Lab 6

Reflection

We have worked our way up from DFAs to TMs. In each case we saw the limitation and add something to address it.

Now, try and think about the journey backwards:

  • What do you need to remove from TMs to get PDAs?
  • What do you need to remove from PDAs to get NFAs?
  • Why would we want to study some of these simpler models despite their limitations?
Hints
  • TM -> PDA Ability to read and write as often as needed without any restriction, even after the input has been read fully.
  • PDA -> NFA Ability to store an arbitrary amount of data (in a restricted memory structure).

  • TMs can either halt (and accept/reject) or loop (never halt). This creates difficulties in guaranteeing some desirable properties about them, most notably "whether a TM will halt or not" (which we will see next week).

    On the other hand, DFAs are very predictable and we can almost guarantee the properties we need.

    PDA fall half-way between the two.

Info

You don't have to hand-in your reflection -- this is not an assessment. Keep your notes and go over them as you understand the material more. Some of the above ideas will become clear in one week, while others will be met again towards the end of the module!