2024 TOC (CS and IT) Course Page

Theory of Computation, January 2024 - April 2024

Instructor Details

Name: Ajaya Kumar Dash
Email:
Address:
- CG-19, Ground Floor, IIIT Bhubaneswar (Faculty chamber)
- Augmented Reality Lab, 1st Floor, C-Block, IIIT Bhubaneswar (Lab)

Branch-wise Class Schedule ( ≈ 3 hrs per Week )

Day → Branch ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
CS	09:30 am	-	09:30 am	09:30 am	-	-	-
IT	-	09:30 am	-	11:30 am	10:30 am	-	-

Syllabus

Find the syllabus by visiting the link. [ Download ]

Books

Reference Books

R1. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Pearson, 2008.
R2. Michael Sipser, Introduction to the Theory of Computation, 3rd Edition, Cengage India, 2014.
R3. John C. Martin, Introduction to Languages and the Theory of Computation, 3rd Edition, McGraw-Hill Higher Education, 2002.
R4. Peter Linz, An Introduction to Formal Languages and Automata, 7th Edition, Jones & Bartlett Publishers, Inc, 2022.

Evaluation

Assignments

Assignment 01: Find the regular expressions
- Release date: March 12, 2024
- Due date: Next Class
- [ View Assignment ]
Assignment 01-Extension: Along with the regular expressions of the questions in Assignment 01, design the DFA for all the questions.
- Due date: March 18, 2024 (8:00 pm, IST)
- The submission file must be in .pdf format with the following naming convention
  - For CS(A) branch: [Student Id]_TOC_Assignment01_CS_A.pdf
  - For IT branch: [Student Id]_TOC_Assignment01_IT.pdf
- Use the following links to submit your submission.
  - For CS(A) branch: Click Here
  - For IT branch: Click Here

Some Groundbreaking Articles and A Well Documented Book

[1936, Article] The famous paper by A. M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. 👉 Click Here
[1955, Article] George H. Mealy: A method for synthesizing sequential circuits, The Bell System Technical Journal. 👉 Click Here
[1958, Article] Edward F. Moore: Gedanken-experiments on sequential machines, Journal of Symbolic Logic. 👉 Click Here
[1971, Article] The celebrated paper by Stephen A. Cook: The Complexity of Theorem-Proving Procedures. 👉 Click Here
[2012, Book ] A book by S. Barry Cooper and Jan Van Leeuwen: Alan Turing: His Work and Impact. 👉 Click Here

Course Progress and Resources

Attention: Sometimes, the size of the lecture slide is large and may take some time to load depending on the internet speed. The instructor is suggesting you to develop a habit of reading the text/reference book(s)!!

Sl No #	Date	Time	Duration	Reading List and Resources	Contents Discussed
01	-	-	1.0 hr	◦ View Lecture Slide	Informal discussion: Course overview, motivation behind this course, prerequisites, lesson plan
-	-	-	NA	◦ [R1] Section 1.2–1.4	Introduction to different formal proof techniques.
02	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 1.5	A bird’s-eye view to formal language and automata theory, limitation of computing overview, basic terminologies, formal definitions: alphabet, grammar, string, language
03	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 2.1, 2.2	Definitions revisited in detail, formal definition of finite automata (deterministic), an example of a deterministic finite automata
04	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 2.1, 2.2	DFA definition revisited, Some examples on minimal DFA construction, string acceptance, languange acceptance
05	-	-	1.0 hr	◦ View Lecture Slide	(Cont…) Examples on DFA design
06	-	-	1.0 hr	◦ View Lecture Slide	(Cont…) Examples on DFA design
07	-	-	1.0 hr	◦ View Lecture Slide ◦ [R4] Section 2.1	Complement of DFA: definition, language accepted by the complemt of a DFA, design of DFA using the idea of complementation
08	-	-	1.0 hr	◦ View Lecture Slide	Examples on the DFA design using the concept of union, intersection and difference
09	-	-	1.0 hr	◦ View Lecture Slide	Creating DFA for real problems
10	-	-	1.0 hr	◦ View Lecture Slide ◦ [R4] Section 1.2	Reprentation of language using grammar: Definition of a grammar, variables, terminals, start variable, production rules; languages generated by grammar, sentential forms of derivation; example and proofs to find the language represented by a grammar
11	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 2.3	Nondeterministic finite automata (NFA): definition, necessity of NFA over DFA, examples
12	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 2.3	Equivalence between NFA and DFA, conversion of NFA to DFA using subset construction method, examples
13	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 2.5	NFA with 𝜺 transitions, 𝜺-closure, equivalence between 𝜺-NFA and NFA, an example; Complementation of NFA
14	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 2.4	Minimisation of DFA: State eliminination method (idea and examples)
15	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 4.4	Minimisation of DFA: Table filling method (idea and examples): A Myhill-Nerode Theorem Application
16	-	-	1.0 hr	◦ View Lecture Slide ◦ (Read) [1955,Melay] ◦ (Read) [1958,Moore]	Finite automata with output: Overview of Moore and Melay machine; Moore and Melay machine construction examples
17	-	-	1.0 hr	◦ View Lecture Slide ◦ [R1] Section 3.1	Regular languages, regular expressions, regular operators and precedence, basic regular expressions and equivalent languages, related proofs
18	-	-	-	◦ Assignment 01	Check the assignment section of this page.
19	-	-	-	◦ View solution	Solution of assignment 01
20	-	-	1.0 hr	◦ View Lecture Note ◦ [R1] Section 3.2	Conversion of regular expression to finite automata and vice-versa, Arden’s lemma and examples.
21	-	-	1.0 hr	◦ View Lecture Note ◦ [R1] Section 3.2	Conversion of finite automata to regular expression: State elimination method and examples.
22	-	-	1.0 hr	◦ View Lecture Note ◦ [R1] Section 4.2, 4.3	Closure properties of regular languages, Some selected properties and their proofs.
23	-	-	1.0 hr	◦ View [Note1] [Note2] ◦ [R1] Section 4.1 ◦ [R4] Section 4.3	Identifying whether a language is regular or not? Pigeon hole principle and example; Pumping lemma theorem, proof, and example on Pumping lemma.
24	-	-	1.0 hr	◦ View Lecture Note	More examples on Pumping lemma.
25	-	-	1.0 hr	◦ View Lecture Note ◦ [R4] Section 5.1, 5.2	◦ Derivation, sentential forms in grammar, Chomsky hierarchy (type-0, type-1, type-2, type-3) for languages and grammars. ◦ (Read) Context free grammars, parsing and ambiguity.
26	-	-	1.0 hr	◦ View Lecture Note ◦ [R4] Section 6.1	Context Free Grammars(CFG) and Context Free Languages(CFL), properties of CFG, Simplification of CFG (removing useless symbols, 𝜺-productions, and unit productions).
27	-	-	1.0 hr	◦ View Lecture Note ◦ [R4] Section 6.2	Normal forms for Context Free Grammars (CFG): Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).
28	-	-	1.0 hr	◦ View Lecture Note ◦ [R4] Section 6.3	Membership algorithm for context free grammars: CYK algorithm.
29	-	-	1.0 hr	◦ View Lecture Note ◦ [R4] Section 7.1 – 7.4	Pushdown automata(definition and design), non-deterministic and deterministic pushdown automata(PDA), relationship of PDA with CFL.
30	-	-	NA	[R4] Section 8.1 and 8.2.1	(Read) Pumping lemma for CFLs, closure properties of CFLs.
31	-	-	1.0 hr	◦ View Lecture Note ◦ [R4] Section 9.1 – 9.3	◦ Turing machine(definition), Examples on Turing machine construction. ◦ Turing machine as language acceptors and transducers. ◦ (Read) Turing’s Thesis.

👉 Note: The lack of uniformity in the arrangement of the various lecture slides and notes makes it visually unappealing to have them combined into a single document. Therefore, the consolidated file comprising all the notes will not be uploaded.