Weightage | 10% |
Weightage - Part A | 7% |
Weightage - Part B | 18% |
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 |
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 |
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.
[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.
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.
[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.
[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
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 -
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}.
[Picked up from random internet searches] Give deterministic finite automata accepting the following languages over the alphabet {0,1}.
[Hopcroft and Ullman, pg. - 48, from 2.5] Give deterministic finite automata accepting the following languages over the alphabet {0,1}.
[Hopcroft and Ullman, pg. - 50, from 2.10] Give deterministic finite automata accepting the following languages over the alphabet {0,1}.
Miscellaneous
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%
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 |