26/12/23	Some videos of portions from modules 4 and 5 will be posted here. Chomsky Normal Form of CFGs 1. CNF Video 1   175MB  -- Audio may not be good at the beginning etc. 2. CNF Video 2   114MB 3. GNF Video  10MB  -- Very short video. Only introductory. Conversion from and to GNF are not covered. 4. Language Classes & Decidability   24MB -- Must watch 5. Halting & Decidability  32MB  -- Must Listen (27/12) 6. Variants of TMs 85MB - Multitrack, Multitape, Nondeterministic, Universal. Detailed explanation of UTM. (Ignore syllabus displayed here and there). Recommended to watch. 7. Video7 72MB -- UTM, Universal Language, and Decidability. And Closure properties of TMs(The last part may be optional). 8. Video8 63MB --  Halting problem, Closure properties of Recursive, RE Languages,  Some decidable and undecidable problems. Worth listening. 9. CNF example 8MB -- Converting a simple CFG to CNF format without going through formal steps, as the example is very simple. Very small video. 10. CSG LBA 47MB -- Chomsky hierarchy, RG, CSG, LBA, ..., Some REL properties.  Useful.                         (End)
Syllabus	.html           .pdf
Students' List	s5d
Contact  Hours (@409)	3/8 21/8 4/9 18/9 Monday 5 3 5 2 Tuesday 6 Wednesday 3 1 1 3 Thursday 4 1 4 1 Friday 6 6 5
Progress	Course Progress Page
Assignments	21/11/23. CA1 is scheduled for 24/11/23 2PM. Rescheduled to 28/11 3PM, as requested by students. CA1 Model QP:  Design a context free grammar for the following language over {a,b}. L1 = {aibj | i ≠j} (i.e.  Set of strings with some a's followed by some unequal number of b's) Draw the parse tree for a member of L1 with size 3. Venue will be informed later. Instructions: Write answer to the above question on your own in advance and carry it in one sheet of paper to the test hall for reference. Answers written by some one else may not help you much. No need to attach it with the test answer sheet.  Only one sheet is required for writing the answer - which you should bring. Write your name and other details in advance, You may carry one more sheet of paper for work out. Do not bring any other material to the test hall. Neatly write the answer in the stipulated time. No discussion or exchange of material with others are permitted. Please don't abstain. Re-chance will not be an easy choice. 28/11: Questions asked for CA1 today: Design a context free grammar for the following language over {a,b}. Then draw the parse tree for a member of L with size 3. For odd roll numbers L= {aibj | i>j>0} For even roll numbers L= {aibj | 0<i<j} --------------- Answer keys Model Q: S --> AC | CB C --> aCb | $\epsilon$ A --> aA | a B --> Bb | b CA1 : Odd roll numbers S --> aACb C --> aCb | $\epsilon$ A --> aA | a CA1: Even roll numbers S --> aCBb C --> aCb | $\epsilon$ B --> Bb | b ------------------- CA1 Marks 7/12 CA2 is scheduled for 14/12 9.30AM Model Question for CA2: Design a Turing Machine to accept the language {0m110n : m ≠ n; m,n>0} 8/12: Sanin and Akshara had informed me that there is lab exam scheduled for 14/12. Hence CA1 is postponed to the AN of 14/12. 11/12: Correction: CA2 is scheduled for the AN of 14/12 CA2 Instructions: Write answer to the model question above on your own in advance and carry it in one sheet of paper to the test hall for reference. Answers written by some one else may not help you much. No need to attach it with the test answer sheet.  Only one sheet is required for writing the answer - which you should bring. Write your name and other details in advance, You may carry two more plain sheets for work out. Do not bring any other material to the test hall. Neatly write the answer in the stipulated time. No discussion or exchange of material with others are permitted. Please don't abstain. We may not have time for a re-chance. 13/12: CA2 is scheduled for 14/12/23 3PM 14/12: CA2 Question: (a) Draw the transition diagram of  a TM to accept the language {a^nbcd^(n+k); n>0} over {a,b,c,d} where k= 1+(r%4), where r=your roll number. (b)Write the first 4 ID sequences for th input a^2bcd^(2+k) ------------------- Marks (a) 15 (b) 4 which will used as bonus marks 16/12 CA2 Marks Those who scored bonus marks in CA2 01 15 4 44 15 2 57 15 3 Of these 01, and 44 already have 50 each.  57 will be awarded 3/2=1.5 marks extra.
Tests	Topics for T1: Modules  1 and 2. i.e. Everything related to what we have discussed in class. Answer clearly and legibly. Please do not abstain. No retest will be allowed if reason is not convincing enough. 25/10:  T1 evaluations have been completed. Answers will be discussed in class. T1 Marks. Check them and claim your marks if you feel that current marks are less than what it should be. So, for that, be well prepared about the questions and answers and put forth valid logical arguments. Requests like "could you explain where I lost marks so that I can improve next time" will not be entertained normally. All of you are requested to check the answer papers and ensure that you get rewarded with the marks you are eligible for. Entries exist in tabulation sheet only if some marks are scored against that question. Emails in this regard also will not be entertained for the time being as personal interactions are required to discuss queries if any, properly. If you wish you can capture the photo of the answer paper and come back later to settle doubts if any. 30/11: Topics for T2: Modules  3 and 4 :- Everything related to what we have discussed in class. Answer clearly and legibly. Please do not abstain. No retest will be allowed if reason is not convincing enough. 9/12 T2 Marks
Sessional	10/12/23 The sessional mark calculations based on the scores of T1, T2, A1, Att along with possible minimum (.5) and possible maximum (7.5) marks for A2 are ready. The last column indicates the minimum/maximum sessional marks. (1) Minimum sessional  :::  If appeared for CA2. (2) Maximum sessional   ::: If scored full marks in CA2. 16/12   T1 Marks           T2 Marks        CA1 Marks      CA2 Marks        Attendance T1R Marks    CA1R Marks Provisional sessional marks Marks have been Finalized. And entered into KTU portal.
Attendance	Students are expected to attend all the classes. Please be there at the class at the time of commencement. Attendance shall be marked only if physically present in the class. As per KTU rules, absence for all activities and contingencies should be limited to 25%. Also, late comers will be marked, and two late marks will count as one absence.  Attendance at the end of Sept/23 Attendance shortage at the end of Sept/23 67 10   71 63 10   71 53 10   71 39 10   71 33 10   71 23 10   71 15 10   71 6 9   64 28 9   64 20 9   64 35 8   57 12 8   57 Attendance at the end of Oct/23 Attendance shortage at the end of Oct/23 55 18   72 20 18   72 12 18   72 Attendance at the end of Nov/23 (Shortage list below. Duty leaves not yet processed) 12 27   73 63 26   70 55 26   70 7/12/23 Attendance at the end of regular classes today (Before considering duty leaves) Shortage list (Before considering duty leaves) 55 30   73 63 28   68 As per attendance rules, 8.2, attendance up to  10% can be considered for national level duty leave. As per attendance rules, 8.3, attendance up to  5% can be considered for college level duty leave. (Correct me if not correct!) Duty Leave Requests under consideration * indicates subject to verification IEDC,Oct12 22 Chess.Nov22 22 55 Chess.Nov23 55 NCC.Oct26 55 16 NCC.Oct27 55 16 Sports.Nov3 55 IHRD.Sept21*  51 52 39 41 NSS.Aug16 2 3 6 9 12 14 15 18 19 23 32 33 38 57 65 TPC.Sept21 23 28 33 50 TPC.Sept25 23 28 33 50 8 15 Concerns if any please bring to my notice immediately -------------------------------------------------------------------------------- Updated attendance data based on duty leave also(Again subject to verification) Shortage 63 28   68.29 6.21PM IHRD.Sept21*  51 52 39 41 (Proof is pending) 7:16PM Contents updated after disregarding IHRD.Sept21*  51 52 39 41 May not affect 51 52. But, may slightly affect 39 41
Course Schedule	Required: M1 M2 M3 M4 M5 T A E Tot 2/8 9 9 10 8 9 4 3 52 13/9 1 53 30/11 10 8 10 6 9 4 2 1 50 Max Possible/Available: Aug Sep Oct Nov Dec Tot 2/8 16 17 19 22 14 88 13/9 9 6 19 22 4 60 16/10 9 5 8 21 4 47 1/11 9 5 11 16 4 45 21/11 9 5 11 12 4 41 30/11 9 5 11 12 4 41

/Announcements/Information

25/07/23	Official date of commencement  - 3/8/23 Class ends on - 20/12/23       7/12/23
6/10/23	We will not have our session today(6/10/23) 2PM online/offline as election is scheduled for 2.30PM. Most probably we will have an online session tomorrow(7/10/23)  7PM. Will confirm by 2.30PM tomorrow.
7/10/23	Due to some personal inconvenience there will not be any online session today. Also the Monday 2nd hr session will be handled by Prof. Betty.
10/10	Day's hour 6 session will be handled by Prof.Vishnu
7/12/23	Regular classes end today. CA2 is scheduled for 14/12/ 9.30 AM Retests for all tests/assignments have been scheduled for 2PM, 14/12/23.
8/12	Sanin and Akshara had informed me that there is lab exam scheduled for 14/12. Hence CA1 is postponed to the AN of 14/12. Also, the re-appearance chance for T1, T2, CA1, in that case has to be scheduled sometime  during 11/12 and 13/12. Affected students are requested to inform me a proper schedule for this. Also, they have to submit the written approved request.
11/12	I have so far received only one request with respect to re-appearance chances for T1, T2, and CA1. I will not be able to complete the required preparations, if requests and other relevant information if any are not received in advance.   Hence I shall not be responsible if you miss the opportunity due to the omission from your side. Correction: CA2 is scheduled for the AN of 14/12
13/12	Schedule for 14/12 Assessment Time For Venue CA1 R 10 -- 11 4 63 (Lab2/SDPK Room . Please find me!) CA2 3 -- 4 All Will inform at 1PM tomorrow T1R 4.30 - 6.30 16 55 At my cabin T2R 4.30 - 6.30 63 At my cabin
14/12	2.05PM Venue will be informed shortly 2.40PM RNs  <36 @501 Rns  >35 @502