Formal Languages and Automata Theory

Spring 2016 COT4420 HW2

Name:___________

1) Create an NPDA that will accept all strings w such that

(na(w) = nb(w)) There are the same number of a's and b's.

2) Create an NPDA that will accept all strings w such that

(na(w) = nb(w)∙2) or (nb(w) = na(w)∙2). (There are twice as many

a's as b's or there are twice as many b's as a's.)

3) Draw a Turing Machine (showing the states and transitions)

that will take a unary number and divide it by three (using

integer division).

4) Prove that there is at least one problem that cannot be

solved.

5) Define P.

6) Give two definitions for NP.

7) Define NP complete.

8) How can you prove that a problem is NP complete?

9) Prove that there are more real numbers between 0 and 1.0

then there are natural numbers.

10) Everyone gets an A for both HW's! So don't bother turning

this in. Good luck on the final exam.