University of Minnesota
CSCI4011: Automata, Computability & Complexity
index.php

CSci 4011: Automata, Computability & Complexity

Homework 3

Homework assignments are to be completed alone and without assistance (except from TAs and the Instructor). Write your discussion section number (e.g. “discussion 3”) at the top of your work.

Due in gradescope as a PDF.

Do the following exercises/problems from the class textbook. Show all your reasoning for full credit.

Chapter 1

1.29(b)

Chapter 2

2.1, 2.4(b,c,e,f), 2.9

Chapter 3

3.6

Chapter 4

4.2, 4.3