CS205M has moved to Moodle. Kindly login to Moodle with your Webmail credentials and subscribe to CS205M.

CS205M : Theoretical Foundations of Computer Science

• Syllabus : http://www.iitg.ernet.in/cse/csecourses/?courseCode=CS205M

• Class Timings : Mon-Wed-Fri 12:00pm-12:55pm 2204.

• References : My primary reference will be Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. When I studied the material, I followed this book and hence I am biased towards this. But, as you will find out over the duration of the course, all of the material is extremely standard and can be studied from any book dealing with finite state machines. All the references given in the syllabus page are equally adept at handling the material of the course. Moreover, since proofs are not subjective, any proof technique from any book is acceptable for the course.

• Instructor : Deepanjan Kesh(deepkesh@)

• Teaching Assistants : Rahul Kuman Kundra(r.kundra@), Ranjan Mandal(ranjan@), Debanjan Sadhukhan(debanjan@)

• Evaluation : There will be three examinations. Two of them will be the usual midsem and endsem as decided by academic section, each contributing 30% towards your final score. There will be another exam, to be held towards the end of the course, which will be open time and will contribute 40% towards your score. At the end of the term, your marks will be scaled down to 100. You will require atleast 40 to pass the course. For other grades, I will resort to relative grading. This comes with its own pros and cons - if the class is doing very well, I wont shy away from giving AAs to everybody. On the other hand, if I feel that none of you have grasped the concepts well, then I might not award a single AA.

• Assignments : There will not be any assignments given for this course. Instead, the Problems section will be populated gradually over the duration of the course. Your exam performance will be strongly correlated to the percentage of the problems you can solve. You can also contribute towards the problem pool. If you have found out some problems that you found interesting, kindly bring it to my notice. If it is nontrivial, I will add to this page with proper credits to the contributor.

Problems

• 12-AUG-2012

  • [Automata, Computability and Complexity by Elaine Rich, Pg. 122-123] Give finite automata accepting the following languages over the alphabet {0,1}.

    • The set of all strings where every 0 is immediately preceded and followed by 1.
    • The set of all strings that does not end in 01.
    • The set of all strings that has neither 01 nor 10 as substrings.
    • The set of all strings that contain at least two 1's that are not immediately followed by an 0.
    • The set of all strings that contain no more than one pair of consecutive 0's and no more than one pair of consecutive 1's.
    • The set of all strings that begins and ends with the same symbol.
    • The set of all strings that contain both 101 and 010 as substrings.
    • The set of all strings of the form a^mbaⁿ such that n-m mod 3 = 0.

  • For all the problems you have solved by constructing a non-determinitic finite automata, try to come up with a deterministic machine for the same.

• 06-AUG-2012

  • [Picked up from random internet searches] Give deterministic finite automata accepting the following languages over the alphabet {0,1}.

    • The set of all strings containing either even number of 0's or odd number of 1's but not both.
    • The set of all strings containing the substring 0110.
    • The set of all strings containing zero of more occurances of the substring 0110.
    • The set of all strings not containing the substring 0110.

  • [Hopcroft and Ullman, pg. - 48, from 2.5] Give deterministic finite automata accepting the following languages over the alphabet {0,1}.

    • The set of all strings ending in 00.
    • The set of all strings with three consecutive 0's.
    • The set of all strings such that every block of five consecutive symbols contains atleast two 0's.
    • The set of all strings beginning with a 1 which, interpreted as the binary representation of an integer, is congruent to zero modulo 5.
    • The set of all strings such that the 4^th symbol from the right end is 1.

  • [Hopcroft and Ullman, pg. - 50, from 2.10] Give deterministic finite automata accepting the following languages over the alphabet {0,1}.

    • The set of all strings with at most one pair of consecutive 0's and at most one pair of consecutive 1's.
    • The set of all strings with an equal number of 0's and 1's such that no prefix has two more 0's than 1's nor two more 1's than 0's.

• 25-JUL-2012

  • Prove that a ordered directed tree cannot have cycles.

  • Prove that there cannot exist any bijection between the set of integers and the set of reals.

  • [Hopcroft and Ullman, pg. - 50, from 2.10] Write regular expressions for -

    • The set of all strings with at most one pair of consecutive 0's and at most one pair of consecutive 1's.
    • The set of all strings with an equal number of 0's and 1's such that no prefix has two more 0's than 1's nor two more 1's than 0's.