# 4.5 Lab 4

## Objectives

The goal of this lab is to **evaluate** your ability to:

- read and write DFAs
- read and write Turing Machines
- prove the correctness and efficiency of algorithms

## Tasks

- write a dfa
- write a turing machine
- prove that the algorithm works
- prove the time and space complexity of the algorithm
- something more??