2023 TOC (CS and CE) Course Page

Theory of Computation, January 2023 - April 2023

Instructor Details

Name: Ajaya Kumar Dash
Email:
Address:
- CB-51, Faculty chambers, IIIT Bhubaneswar (Office).
- 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	-	-	10:00 am	02:00 pm	12:00 pm	-	-
CE	11:00 am	-	-	10:00 am	03:00 pm	-	-

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, 6th Edition, Jones & Bartlett, 2016.

Evaluation

Assignments

Assignment 01 ~~(Due date: 30-March-2023 05:00 pm IST)~~
- Check the examples from class 19 and design the DFA for all the 40 examples from that class note. If it is not possible to design the DFA for any of the example(s), give a justified reason why you think so.
- NOTE
  - Use the LaTeX typesetting system to record your solutions. A sample LaTex template to submit the solution can be downloaded by clicking here. This template was used for the submission of DAA assignment earlier. Change the necessary contents of the template as per your need.
  - ~~An upload link will be activated on the due date to submit your solution in pdf format.~~
  - Make sure to keep the final document ready by the due date.
  - There is no relaxation for the late submission in any circumstances. In case of late submission, zero marks will be awarded.
- Depending on your branch, follow the appropriate link to upload the necessary file. The link will accept the responses up to 6 Pm (IST), on 30-Mar-2023.
  - CS Branch: [Upload here]
  - CE Branch: [Upload here]

Some Fundamental Articles

[1936] The famous paper by A. M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. 👉 Click Here
[1971] The celebrated paper by Stephen A. Cook: The Complexity of Theorem-Proving Procedures. 👉 Click Here

Course Progress and Resources

Sl No #	Date	Time	Duration	Reading List and Resources	Contents Discussed
00	-	-	1.0 hr	◦ ~~Class Lecture~~	Course overview and motivation behind this course.
01	-	-	NA	◦ [R1] Section 1.2, 1.3, 1.4	Introduction to different formal proof techniques.
02	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 1.5	A bird’s-eye view to formal language and automata theory, Basic terminology: alphabets, strings, string operations, power of alphabet, languages, finite automata definition, example of a simple finite automata.
03	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.1, 2.2	Deterministic finite automata (DFA), transition and extended transition functions, example of a minimal DFA construction, idea of string and language acceptance.
04	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.1, 2.2	Some examples on minimal DFA construction.
05	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.1, 2.2	More examples on minimal DFA construction continued.
06	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.1, 2.2	◦ (Continued) Some more examples on minimal DFA construction. ◦ (HW) An application to text search using FA (Section 2.4 of R1)
07	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.2 ◦ [R4] Section 2.1	Languages accepeted by DFA and it’s complement language, some examples on DFA design using complementation concept, definition of regular languages, example to show a language to be regular.
08	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R4] Section 1.2	Language representation, Definition of a grammar: variables, terminals, start variable, production rules; languages accepted by grammar, sentential forms of derivation, example and proofs to find the language represented by a grammar.
09	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R4] Section 1.3	Some Applications of automation (Grammar for variable identifier in C, finite automation for all legal C identifiers, automation for n-bit binary adder).
10	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.3 (2.3.1 to 2.3.4)	Non-deterministic finite acceptors (NFA): definition, necessity of NFA over DFA, examples.
11	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.3 (2.3.5, 2.3.6)	Equivalence between NFA and DFA, subset construction method from NFA to DFA, some examples.
12	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 2.5	NFA with 𝜺 transitions, 𝜺-closure, equivalence between 𝜺-NFA and NFA, an example.
13	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R4] Section 2.4	Construction of DFA from NFA, Complementation of NFA, Minimization of DFA states (State elimination method and examples).
14	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 4.4	Myhill-Nerode Theorem (HW), Minimization of DFA states (Table filling method and examples).
15	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ (Read) [Orig. Article]	Finite automata with output: Overview of Moore and Melay machine, Moore machine construction with examples.
16	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ (Read) [Orig. Article]	Finite automata with output: Melay machine construction with examples.
17	-	-	1.0 hr	◦ ~~Class Lecture~~	Finite automata with output: Moore and Melay machine equivalence, conversion of Moore machine to Melay machine and vice versa.
18	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 3.1	Regular languages, regular expressions, regular operators and precedence, basic regular expressions and equivalent languages, related proofs.
19	-	-	1.0 hr	◦ ~~Class Lecture~~	(Assignment 01) Examples on regular expressions.
20	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 3.2.1, 3.2.3	Conversion of regular expression to finite automata and vice-versa, Arden’s lemma and examples.
21	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 3.2.2	Conversion of finite automata to regular expression: State elimination method and examples.
22	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R1] Section 4.2, 4.3	Closure properties of regular languages, Some selected properties and their proofs.
23	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [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	◦ ~~Class Lecture~~	Some more examples on Pumping lemma.
25	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [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	◦ ~~Class Lecture~~ ◦ [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	◦ ~~Class Lecture~~ ◦ [R4] Section 6.2	Normal forms for Context Free Grammars (CFG): Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).
28	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R4] Section 6.3	Membership algorithm for context free grammars: CYK algorithm.
29	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R4] Section 7.1, 7.2, 7.3, 7.4	Pushdown automata(definition and design), non-deterministic and deterministic pushdown automata(PDA), relationship of PDA with CFL.
30	-	-	2.0 hrs	[R4] Section 8.1 and 8.2.1	(Read) Pumping lemma for CFLs, closure properties of CFLs.
31	-	-	1.0 hr	◦ ~~Class Lecture~~ ◦ [R4] Section 9.1, 9.2, 9.3	◦ Turing machine(definition), Examples on Turing machine construction. ◦ Turing machine as language acceptors and transducers. ◦ (Read) Turing’s Thesis.

Previous Year End-semester Solutions

You can find the reference solution to the previous year TOC end-semester examination.
- [ View the answers ]