CS 201 Homeworks
Homeworks are due at the start of class. If for some reason you are unable to submit your homework to me in class then you must either bring it to my office (placing it under the door if the door is closed) or place it in my mailbox (S. Goldman) in Bryan 509 AT LEAST 15 mintues before the start of class on the day the homework is due.
o Homework 0 --- Due on Friday August 28

o Homework 1 --- Due on Wednesday September 9

o Homework 2 --- Due on Wednesday September 16

o Homework 3 --- Due on Wednesday September 30

o Homework 4 --- Due on Wednesday October 7

o Homework 5/6 --- Due on Wednesday October 28

o Homework 7 --- Due on Wednesday November 4

o Homework 8 --- Due on Wednesday November 18

o Homework 9 --- Due on Wednesday December 2

o Homework 10 --- Due on Wednesday December 9

o Practice Excercises for the Final

SOLUTIONS for Problem 1: What is the language recongized by the following DFAs?
1a. There was an error in this problem in that both transitions leading out of S0 were labelled with a 1. Here are the solutions for both possibile corrections you may have made:
solution


solution

1b
1b solution

SOLUTIONS for Problem 2: For each of the following languages, either give a DFA that recognizes the language (i.e. a DFA M, such that L(M) is the desired language) or prove that no DFA can recognize the language. All languages are defined over the set of all bit strings.

2a: Let L1 consist of strings that have n zeros followed by 2n ones where n is a natural number. 2a solution

2b: Let L2 consist of strings that have an even number of 1s and an odd number of 0s. 2b solution

2c: Let L3 consist of strings in which there are never two consecutive 0s and there are never two consecutive 1s. 2c solution

2d: Let L4 consist of strings that has exactly 3 times as many 0s has it has 1s. 2d solution

Return to the CS201 Home Page