# CS203 : Formal Languages and Automata Theory

## 06-APR-2013

• Mid Semester Examination
 Weightage 10%
• First Open Time Examination
 Weightage - Part A 7% Weightage - Part B 18%
• Second Open Time Examination
 Date Sunday, 14-APR-2013 Time 08:00am - Midnight Venue Your cubicle in CSE Laboratories Weightage 35% Total Marks in Question Paper 62 Full Marks 42 Number of Questions 1+6 Type of questions Interesting and hopefully unfamiliar
• End Semester Examination
 Weightage 30% Total Marks in Question Paper 27 Full Marks 17 Number of Questions 1+5 Type of questions Results done in class and perhaps one trivial, yet unfamiliar, question

## 31-MAR-2013

• First open time examination's question paper can be found here.
• Yet another assignment can be found here.

## 28-FEB-2013

• Mid semester question paper can be found here.
• An example of how to write proofs for Context free grammars can be found here.

## 20-FEB-2013

• Details of First Open Time Examination -
 Date Saturday, 02-MAR-2013 Time 08:00am - Midnight Place To be announced

## 16-FEB-2013

• A model mid semester question paper can be found here.

• An ode to pumping lemma by Vivek Bhargav can be found here.

## 23-JAN-2013

### Announcement

• You can find lectures delivered by Prof. Jeffrey D. Ullman himself here.

• Consider the following problem from Assignment 2 -
[Hopcroft and Ullman, Pg.-72] Let L be any subset of 0*. Prove that L* is regular.
You are welcome to send in your proofs in pdf format, and the best solution with the most lucidly written proof will get a Cadbury's Dairy Milk and have his/her solution uploaded in the course website.

### Assignment 3

Note: Though we have not discussed the notion of non-deterministic PDA's with ε-transitions, you are encouraged to try and come up with PDA's for the following languages.

• [Hopcroft and Ullman, Pg.-103] Construct context-free grammars for the following sets.

• The set of palindromes over the alphabet {a,b}.
• The set of all strings of balanced parentheses, i.e., each left parenthesis has a matching right parenthesis and pairs of matching parentheses are properly nested.
• The set of all strings over alphabet {a,b} with exactly twice as many a's as b's.
• The set of all strings over alphabet {a,b} not of the form ww for some string w.
• {aibjck | i ≠ j or j ≠ k}.
• [Hopcroft and Ullman, Pg.-103] Consider the following grammar
S → aS | aSbS | ε.
Prove that the language generated by the grammar is same as
{ x | each prefix of x has at least as many a's as b's} .

• [Hopcroft and Ullman, Pg.-103] Construct context-free grammar for the following set.
{ w#wR# | w is a string in (0+1)+ }.
Here, (0+1)+ = (0+1)* - {ε}.

• [Hopcroft and Ullman, Pg.-103] For i ≥ 1, let bi denote the string in 1(0+1)* that is the binary representation of integer i. Construct a CFG generating
{0,1,#}+ - { b1#b2#⋅⋅⋅#bn | n ≥ 1 }.
Here, (0,1,#)+ = (0,1,#)* - {ε}.

• [Elaine Rich, Pg.-246] Construct context-free grammars for the following sets.

• { aibj | 2i = 3j + 1 }.
• { aibj | 2i ≠ 3j + 1 }.
• { ai bj ck | i, j, k ≥ 0 and (k ≤ i or k ≤ j) }.
• { an bm | m ≥ n, m-n is even } }.
• { am bn cp dq | m, n, p, q ≥ 0 and m+n = p+q }.
• { bi # b{i+1}R | bi is the binary representation of some integer i, i ≥ 0, without leading zeros }. (For example, for i = 5, b5 = 101. Then 101#011 is a valid string)
• { xR # y | x,y are strings in {0,1}* and x is a substring of y }.

## 09-JAN-2013

### Assignment 2

• [Hopcroft and Ullman, Pg.-72] Let L be a regular set. Which of the following sets are regular? Justify your answers.

• { a1a3a5 ··· a2n-1 | a1a2a3a4...···a2n is in L }.
• { a2a1a4a3···...a2na2n-1 | a1a2a3a4 ··· a2n is in L }.
• CYCLE(L) = { x1x2 | x2x1 is in L for strings x1 and x2 }
• MAX(L) = { x in L | for no y other than ε is xy in L }
• MIN(L) = { x in L | no proper prefix of x is in L }
• INIT(L) = { x | for some y, xy is in L }
• LR = { x | xR is in L }
• { x | xxR is in L }
• [Hopcroft and Ullman, Pg.-72] Show that { 0i1j | gcd(i, j) = 1 } is not regular.

• Let L ⊆ Σ be a language accepted by a finite automaton. Then, construct a finite automaton for the following language - LR = { x | xxR ∈ L }. Here, if x is a string, then xR is defined as the reverse of x. For example, 1010R=0101, 00001R=10000.

• [Hopcroft and Ullman, Pg.-73] Let L be a regular language.

• Define 12(L) to be { x | for some y such that |x|=|y|, xy is in L }. That is, 12(L) is the first halves of strings in L. Prove that 12(L) is regular.
• Is the set of first thirds of strings in L regular? What about the last third? Middle third? Is the set { xz | for some y with |x|=|y|=|z|, xyz is in L } regular? (Note: Proving for the middle third and the last third is substantially harder than proving for the first third)
• [Hopcroft and Ullman, Pg.-72] Let L be any subset of 0*. Prove that L* is regular.

• [Hopcroft and Ullman, Pg.-73] Show that if L is regular, so are

• SQRT(L) = { x | for some y with |y|=|x|2, xy is in L }
• LOG(L) = { x | for some y with |y|=2|x|, xy is in L }

### How to write proofs

I am also uploading a note on how to write proofs. The proof is a solution for 12(L). There are few points I would like to make -

• There is a difference between verifying a proof and understanding a proof. Let me elaborate on that point -

• Verifying a proof is easy. If every step follows from the previous step and previously known results, then your proof is correct.
• Understanding a proof would involve understanding the intuition behind the proof. This part is hard.
• In proofs, you are not obliged to submit the intuition of the proof, but your proof should be lucid enough that people can verify your proof.

• One of the joys of reading someone else's result is to discover the intuition behind the proof.

Let me see if you can discover the basic idea for the solution of 12(L). Once you have done so, you would realise that behind that apparently lengthy proof is an extremely trivial idea.

The document is here.

## 01-JAN-2013

### Assignment 1

• [Automata, Computability and Complexity by Elaine Rich, Pg. 122-123] Give deterministic 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 0m10n such that n-m mod 3 = 0.
• [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 4th 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.
• 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.
• Miscellaneous

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

## 29-DEC-2012

### Syllabus

http://www.iitg.ernet.in/cse/csecourses/?courseCode=CS203

2204

### Class Slots

(Class timings are in green)

 Monday 9:00 am to 9:55 am Tuesday 10:00 am to 10:55 am Wednesday 11:00 am to 11:55 am Friday 8:00 am to 8:55 am

### 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.

### Teaching Staff

 10610103 Badri Prasad Nanda b.nanda@ 126101001 Khushboo Rani khushboo@ 124101017 Pankaj Sachan pankaj.sachan@ 124101018 Jithin K George g.jithin@ 124101006 Sachin Shah sachin.shah@ 124101030 Abhishek Suman abhishek.suman@ 124101032 Vinod Kumar vinod.kumar@ 124101026 Kamaljeet Chauhan c.kamaljeet@

### Evaluation Criteria

#### Weightages

 Mid Semester Examination 10% End Semester Examination 20% First Open Time Examination 35% Second Open Time Examination 35% Make-up Examination

50%

#### How to calculate your final score?

M1 - Normalized marks of Mid Semester Examination.
M2 - Normalized marks of End Semester Examination.
M3 - Normalized marks of First Open Time Examination.
M4 - Normalized marks of First Open Time Examination.
X - Marks (out of 50) in Make-up Examination.

Let M = M1+M2+M3+M4. Then,

 Final Score = M, if M >= 50 50, if M < 50 and M+X >= 50 M+X, if M < 50 and M+X < 50