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

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

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

- Details of
**First Open Time Examination**-

Date | Saturday, 02-MAR-2013 |

Time | 08:00am - Midnight |

Place | To be announced |

A model mid semester question paper can be found here.

An ode to

*pumping lemma*by Vivek Bhargav can be found here.

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.

**Deadline:**27-JAN-2013 Midnight IST

**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*. *{a*.^{i}b^{j}c^{k}| i ≠ j or j ≠ k}

- The set of palindromes over the alphabet
**[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#w*.^{R}# | w is a string in (0+1)^{+}}^{}

Here, (0+1)^{+}= (0+1)^{*}- {ε}.**[Hopcroft and Ullman, Pg.-103]**For*i ≥ 1*, let*b*denote the string in_{i}*1(0+1)*that is the binary representation of integer^{*}*i*. Construct a CFG generating

*{0,1,#}*.^{+}- { b_{1}#b_{2}#⋅⋅⋅#b_{n}| n ≥ 1 }

Here,*(0,1,#)*.^{+}= (0,1,#)^{*}- {ε}**[Elaine Rich, Pg.-246]**Construct context-free grammars for the following sets.- { a
^{i}b^{j}| 2i = 3j + 1 }. - { a
^{i}b^{j}| 2i ≠ 3j + 1 }. - { a
^{i}b^{j}c^{k}| i, j, k ≥ 0 and (k ≤ i or k ≤ j) }. - { a
^{n}b^{m}| m ≥ n, m-n is even } }. - { a
^{m}b^{n}c^{p}d^{q}| m, n, p, q ≥ 0 and m+n = p+q }. - { b
_{i}# b_{{i+1}}^{R}| b_{i}is the binary representation of some integer i, i ≥ 0, without leading zeros }. (For example, for*i = 5*,*b*. Then_{5}= 101*101#011*is a valid string) - { x
^{R}# y | x,y are strings in {0,1}^{*}and x is a substring of y }.

- { a

Badri Prasad Nanda (b.nanda@) | 10020515 | HARSHIT AGRAWAL | harshit@ |
---|---|---|---|

10020524 | MAULISHREE ARVIND PANDEY | maulishree@ | |

10020534 | RISHIKA JAIN | rishika@ | |

11010101 | ABHISHEK SARKAR | abhishek.sarkar@ | |

11010102 | ADITYA KUMAR JHA | j.aditya@ | |

11010103 | AJAY KUMAR KILAKA | a.kilaka@ | |

11010104 | AKSHAY JAJOO | a.jajoo@ | |

11010105 | ANKIT KANWAT | a.kanwat@ | |

11010106 | ARIHANT SETHIA | s.arihant@ | |

11010107 | ARPIT AGRAWAL | arpit.agrawal@ | |

Khushboo Rani (khushboo@) | 11010108 | ARUN BHATI | a.bhati@ |

11010109 | B NITIN CHANDRA | chandra.nitin@ | |

11010110 | B SRIHARSHA | b.sriharsha@ | |

11010111 | BANKURU PRASANNA KUMAR | bankuru@ | |

11010112 | BHANU TEJA GULLAPALLI | g.bhanu@ | |

11010113 | BHAVYA MADAN | bhavya@ | |

11010114 | BINGI NARASIMHA KARTHIK | b.karthik@ | |

11010115 | CHAITANYA AGARWAL | c.agarwal@ | |

11010116 | CHERUKU RAMA KRISHNA | cheruku@ | |

11010117 | CHETAN ANAND | chetan@ | |

Pankaj Sachan (pankaj.sachan@) | 11010118 | GAVVA AVANEESH REDDY | gavva@ |

11010120 | HARSHA SRIMATH TIRUMALA | h.tirumala@ | |

11010121 | HARSHIL LODHI | harshil@ | |

11010122 | HITESH ARORA | a.hitesh@ | |

11010123 | JILLELLA SURENDRANATH REDDY | jillella@ | |

11010124 | JYOTHSNA P | p.jyothsna@ | |

11010125 | K YOSHITHA | k.yoshitha@ | |

11010126 | KANDREGULA S V A RAVI TEJA | kandregula@ | |

11010127 | KARRA DINAKAR REDDY | r.karra@ | |

11010128 | KHANIN DEKA | khanin@ | |

11010129 | KURITI PRASANTH VERMA | kuriti@ | |

Jithin K George (g.jithin@) | 11010130 | M KRISHNA KANTH | m.kanth@ |

11010131 | M PRUDHVI RAJ CHOWHAN | m.chowhan@ | |

11010132 | MADHU PRUDHVI RAJ | r.madhu@ | |

11010133 | MADHURI VITTHAL TIKHE | t.madhuri@ | |

11010134 | MAINAK SETHI | mainak@ | |

11010136 | MASIH TAMSOY | masih@ | |

11010138 | MD SIDDIQ | m.siddiq@ | |

11010139 | MOHAMMED RIYAZ | m.riyaz@ | |

11010141 | MOON SUSHANT SHARAD | m.sharad@ | |

11010142 | MOPURU SANKETH | m.sanketh@ | |

11010143 | MS NEHA DAMADYA | m.damadya@ | |

Sachin Shah (sachin.shah@) | 11010144 | N M HARSHA | n.harsha@ |

11010145 | NAGELLI KARTHEEK | n.kartheek@ | |

11010146 | NAVEEN SAHU | n.sahu@ | |

11010147 | NISHANT YADAV | nishant.yadav@ | |

11010149 | PADIGELA HARSHITH REDDY | padigela@ | |

11010150 | PATHAPATI ROHAN REVANTH SAGAR | pathapati@ | |

11010151 | PERABATHINI MONIKA SRINIVAS | perabathini@ | |

11010152 | PIYUSH DHORE | d.piyush@ | |

11010153 | PUSHPRAJ YADAV | pushpraj@ | |

11010154 | RACHIT KUMAR | k.rachit@ | |

Dileep Reddy (dileep@) | 11010155 | RACHURI ANIRUDH | rachuri@ |

11010156 | RAHUL RAGHAVENDRA HUILGOL | h.rahul@ | |

11010157 | RAKSHITA JAIN | rakshita@ | |

11010158 | ROHAN KUMAR KWATRA | r.kwatra@ | |

11010159 | ROHIT KAMRA | r.kamra@ | |

11010160 | SACHIN AGLAVE | a.sachin@ | |

11010161 | SAGAR PATEL | p.sagar@ | |

11010162 | SHASHANK RAI | r.shashank@ | |

11010163 | SHASHI KANT | s.kant@ | |

11010164 | SHIVAM KUMAR | k.shivam@ | |

Vinod Kumar (vinod.kumar@) | 11010165 | SIMRAT SINGH CHHABRA | simrat@ |

11010166 | SPARSH KUMAR SINHA | sparsh@ | |

11010167 | TUPILI KISHORE | tupili@ | |

11010168 | VEERA ANUDEEP | v.anudeep@ | |

11010169 | VENKATA ABHINAV BOMMIREDDI | v.bommireddi@ | |

11010170 | VISHAL ANAND | vishal.anand@ | |

11010171 | VISHAVDEEP MATTU | vishavdeep@ | |

11010172 | VIVEK BHARGAV | v.bhargav@ | |

11010173 | VIVEK PODDAR | v.poddar@ | |

11010174 | SHYAMAL KEJRIWAL | k.shyamal@ | |

Kamaljeet Chauhan (c.kamaljeet@) | 11010175 | ANCHA VENKATA SIDDHARTH | ancha@ |

11010176 | SHUBHAM LUHADIA | s.luhadia@ | |

11010177 | BASARGE SHREYAS NARENDRA | basarge@ | |

11010178 | CHARANJIT SINGH GHAI | charanjit@ | |

11010179 | SHOBHIT CHAURASIA | c.shobhit@ | |

11010180 | SOUMAK DATTA | soumak@ | |

11020540 | VISHESH KUMAR | k.vishesh@ | |

126201001 | RAHUL GANDOPADHYAY | r.gangopadhyay@ | |

126201002 | RAJESH DEVRAJ | d.rajesh@ | |

126201003 | MRITYUNJAY KUNWER SINGH | kunwer@ |

**[Hopcroft and Ullman, Pg.-72]**Let*L*be a regular set. Which of the following sets are regular? Justify your answers.- {
*a*|_{1}a_{3}a_{5}··· a_{2n-1}*a*is in_{1}a_{2}a_{3}a_{4}...···a_{2n}*L*}. - {
*a*|_{2}a_{1}a_{4}a_{3}···...a_{2n}a_{2n-1}*a*is in_{1}a_{2}a_{3}a_{4}··· a_{2n}*L*}. - CYCLE(
*L*) = {*x*|_{1}x_{2}*x*is in_{2}x_{1}*L*for strings*x*and_{1}*x*}_{2} - 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*} *L*= {^{R}*x*|*x*is in^{R}*L*}- {
*x*|*xx*is in^{R}*L*}

- {
**[Hopcroft and Ullman, Pg.-72]**Show that { 0^{i}1^{j}|*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 -*L*. Here, if^{R}= { x | xx^{R}∈ L }*x*is a string, then*x*is defined as the reverse of^{R}*x*. For example,*1010*,^{R}=0101*00001*.^{R}=10000**[Hopcroft and Ullman, Pg.-73]**Let*L*be a regular language.- Define
to be {^{1}⁄_{2}(L)*x*| for some*y*such that*|x|=|y|*,*xy*is in*L*}. That is,is the first halves of strings in^{1}⁄_{2}(L)*L*. Prove thatis regular.^{1}⁄_{2}(L) - 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)*

- Define
**[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*}

- SQRT(

I am also uploading a note on how to write proofs. The proof is a solution for * ^{1}⁄_{2}(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 * ^{1}⁄_{2}(L)*. Once you have done so, you would realise that behind that apparently lengthy proof is an extremely trivial idea.

The document is here.

[

*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
*0*such that^{m}10^{n}*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 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.
- 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.

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

2204

(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 |

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 :**

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@ |

Mid Semester Examination | 10% |

End Semester Examination | 20% |

First Open Time Examination | 35% |

Second Open Time Examination | 35% |

Make-up Examination |

50%

M_{1} - Normalized marks of Mid Semester Examination.

M_{2} - Normalized marks of End Semester Examination.

M_{3} - Normalized marks of First Open Time Examination.

M_{4} - Normalized marks of First Open Time Examination.

X - Marks (out of 50) in Make-up Examination.

Let M = M_{1}+M_{2}+M_{3}+M_{4}. Then,

Final Score = | M, | if M >= 50 |
---|---|---|

50, | if M < 50 and M+X >= 50 | |

M+X, | if M < 50 and M+X < 50 |