2022 TOC (CS and CE) Course Page

Theory of Computation, August 2022 - November 2022

Instructor Details

Name: Ajaya Kumar Dash
Email:
Address:
- CB-51, Faculty chambers, IIIT Bhubaneswar (Office).
- Augmented Reality Lab, 1st Floor, C-Block, IIIT Bhubaneswar.

Class schedule ( ≈ 3 hrs per Week )

Day → Branch ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
CS	-	~~02:00 pm~~ 12:00 pm	02:00 pm	09:00 am	-	-	-
CE	-	10:00 am	-	03:00 pm	09:00 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, 6th Edition, Jones & Bartlett, 2016.

Evaluation

Mid-semester question pattern

You need to answer all the questions. Find the question-wise mark details below.
- Q1: Five short questions having 2 marks each.
- Q2: Two questions having 5 marks each.
- Q3: Two questions having 5 marks each.

Course Progress and Resources

Sl No #	Date	Time	Duration	Reading List and Resources	Contents Discussed
01	-	-	1.0 hr	Refer Book	Over all course details: Overview of introduction to automation, formal languages, grammar, formal models.
02	-	-	1.0 hr	Chapter 1 of R4	Basic terminology: Alphabets, strings, string operations, power of alphabet, languages, finite automata definition, example of a simple finite automata.
03	-	-	1.0 hr	Refer Book	FA definition revisited, transition and extended transition functions, minimal DFA construction example, idea of string and language acceptance.
04	-	-	1.0 hr	Section 2 of R4	Some examples on minimal DFA construction.
05	-	-	1.0 hr	Refer Book	More examples on minimal DFA construction continued.
06	-	-	1.0 hr	Refer Book	(Continued) Some more examples on minimal DFA construction.
07	-	-	1.0 hr	Refer Book	DFA construction examples, 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	Refer Book	Representation of languages, Definition of a grammar: variables, terminals, start variable, production rules; languages accepted by grammar, sentential forms of derivation, example to get the language of a grammar.
09	-	-	1.0 hr	Refer Book	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	Refer Book	Non-deterministic finite acceptors (NFA): definition, examples.
11	-	-	1.0 hr	Refer Book	Definition: equivalence between NFA and DFA, subset consctruction method from NFA to DFA, some examples.
12	-	-	1.0 hr	Refer Book	NFA with 𝜺 transitions, 𝜺-closure, equivalence between 𝜺-NFA and NFA, some examples.
13	-	-	1.0 hr	Refer Book	Construction of DFA from NFA, Complementation of NFA, Optimization of DFA states (State elimination method and examples).
14	-	-	1.0 hr	Refer Book	Optimization of DFA states (Table filling method and examples).
15	-	-	1.0 hr	Refer Book	Finite automata with output, Overview of Moore and Melay machine, Moore machine construction with examples.
16	-	-	1.0 hr	Refer Book	Melay machine construction with examples.
17	-	-	1.0 hr	Refer Book	Moore and Melay machine equivalence, conversion of Moore machine to Melay machine and vice versa.
18	-	-	1.0 hr	Section 3 of R4	Regular languages, regular expressions, regular operators and precedence, basic regular expressions and equivalent languages, related proofs.
19	-	-	1.0 hr	Refer Book	Examples on regular expressions.
20	-	-	1.0 hr	Refer Book	Conversion of regular expression to finite automata and vice-versa, Arden’s lemma and examples.
21	-	-	1.0 hr	Refer Book	Finite automata to regular expression using state elimination method and examples.
22	-	-	1.0 hr	Chapter 4 of R4	Properties of regular languages, proofs, examples.
23	-	-	1.0 hr	Section 4.3 of R4	Identifying whether a language is regular or not? Pigeon hole principle and Pumping lemma theorem, proofs, examples on Pumping lemma.
24	-	-	1.0 hr	Refer Book	Examples on Pumping lemma(Cont..).
25	-	-	1.0 hr	Refer Book	The Chomsky hierarchy (type-0, type-1, type-2, type-3) for languages and grammars.
26	-	-	2..0 hrs	Chapter 5 of R4	Context free grammars(CFG) and context free languages(CFL), properties of CFG, simplifying CFG(removing useless symbols, 𝜺-productions, and unit productions).
27	-	-	1.0 hr	Section 6.2 of R4	Normal forms for context free grammars (CFG): Chomsky and Greibach normal forms.
28	-	-	1.0 hr	Section 6.3 of R4	Membership algorithm for context free grammars: CYK algorithm.
29	-	-	4.0 hrs	Section 7.1, 7.2, 7.3, and 7.4 of R4	Pushdown automata(definition and design), non-deterministic and deterministic pushdown automata(PDA), relationship of PDA with CFL.
30	-	-	2.0 hrs	Section 8.1 and 8.2.1 of R4	Pumping lemma for CFLs, closure properties of CFLs.
31	-	-	1.0 hr	Section 9.1 of R4	Turing machine(definition), Examples on Turing machine construction: Turing machine as language acceptors and transducers.