Formal Language and Automata Theory, August 2021 (CS)
Find the syllabus by visiting the link. [ Download ]
Note: This evaluation pattern may subject to change due to COVID-19 pandemic.
| Sl No # | Date | Time | Duration | Contents Discussed | |
|---|---|---|---|---|---|
| 1 | 10/08/21 | 10:05am | 1.0 hr | - | A bird’s-eye view to formal language and automata theory |
| 2 | 17/08/21 | 10:05am | 1.0 hr | Class Lecture | Introduction to automation, formal languages, grammar, formal models |
| 3 | 19/08/21 | 09:00am | 1.0 hr | Class Lecture | Alphabets, strings, string operations, power of alphabet, languages, finite automata definition, example of a simple finite automata |
| 4 | 24/08/21 | 10:05am | 1.0 hr | Class Lecture | Definition of FA revisited, extended transition function, Examples to construct minimal DFA |
| 5 | 26/08/21 | 09:00am | 1.0 hr | Class Lecture | Examples to construct minimal DFA |
| 6 | 29/08/21 | 10:00am | 1.0 hr | Class Lecture | Some more examples to construct minimal DFA |
| 7 | 31/08/21 | 10:05am | 1.0 hr | Class Lecture | More examples to construct minimal DFA |
| 8 | 02/09/21 | 09:00am | 1.0 hr | Class Lecture | Examples to construct minimal DFA continued |
| 9 | 03/09/21 | 12:15pm | 1.0 hr | Class Lecture | (Continued) Examples on minimal DFA formation |
| 10 | 07/09/21 | 10:05am | 1.0 hr | Class Lecture | (Continued) Some more examples on DFA |
| 11 | 09/09/21 | 09:00am | 1.0 hr | Class Lecture | 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 |
| 12 | 14/09/21 | 10:05am | 1.0 hr | Class Lecture | Language representation using grammars, 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 |
| 13 | 16/09/21 | 9:00am | 1.0 hr | Class Lecture | Examples on grammars and languages |
| 14 | 17/09/21 | 9:00am | 1.0 hr | Class Lecture | Some Applications of automation (Grammar for variable identifier in C, finite automation for all legal C identifiers, automation for n-bit binary adder) |
| 15 | 23/09/21 | 9:00am | 1.0 hr | Class Lecture | Non-deterministic finite acceptors (NFA): Definition, examples |
| 16 | 24/09/21 | 9:00am | 1.0 hr | Class Lecture | Equivalence between NFA and DFA, Subset consctruction method from NFA to DFA, Examples |
| 17 | 01/10/21 | 9:00am | 1.0 hr | Class Lecture | Construction of DFA from NFA, examples, Complementation of NFA, Minimization of DFA: State elimination method, examples on state elimination method |
| 18 | 05/10/21 | 10:05am | - | - | Mid-semester |
| 19 | 26/10/21 | 10:05am | 1.0 hr | Class Lecture | Minimization of DFA: Table filling method, examples on table filling method |
| 20 | 27/10/21 | 10:05am | 1.0 hr | Class Lecture | FA with output: Introduction to Melay and Moore machine, Basic differences, Some examples on Moore machine |
| 21 | 28/10/21 | 09:00am | 1.0 hr | Class Lecture | Examples on Melay machine |
| 22 | 02/11/21 | 10:05am | 1.0 hr | Class Lecture | Equivalence between Moore and Melay machine: Conversion from Moore to Melay and vice-versa |
| 23 | 11/11/21 | 09:00am | 1.0 hr | Class Lecture | Regular expressions, Regular operators and their precedence, Example of some basic regular expressions, Special cases of emply language and related proofs |
| 24 | 12/11/21 | 09:00am | 1.0 hr | Class Lecture | 40 Probelms on regular expressions |
| 25 | 16/11/21 | 10:05am | 1.0 hr | Class Lecture | Conversion of regular expression to FA and vice-versa, Arden’s lemma for FA to regular expression conversion, some examples on Arden’s lemma |
| 26 | 18/11/21 | 09:00am | 1.0 hr | Class Lecture | State elimination method for FA to regular expression conversion, some examples on state elimination method |
| 27 | 23/11/21 | 05:30pm | 1.0 hr | Class Lecture | Closure properties of regular languanges(union, intersection, concatenation, complementation, star-closure, reversal, homomorphism, prefix etc) and their proofs with examples |
| 28 | 25/11/21 | 05:30pm | 1.0 hr | Class Lecture | Identifying whether a language is regular or not!!, Pumping lemma theorem and it’s proof, Examples on pumping lemma |
| 29 | 26/11/21 | 05:30pm | 1.0 hr | Class Lecture | Examples on pumping lemma (continued … ) |
| 30 | 29/11/21 | 05:30pm | 1.0 hr | Class Lecture | The Chomsky hierarchy (Type-0, type-1, type-2, and type-3) for grammars and languages |
| 31 | 30/11/21 | 05:30pm | 2.0 hrs | Class Lecture | CFG and CFL, Some basic properties of CFG, Simplification of CFG(Removing Useless symbols, epsilon-productions, and unit productions), Some ToDo as home work for students |
| 32 | 31/11/21 | 05:30pm | 1.0 hr | Section 7.1, 7.2, 7.3, and 7.4 of R4 | Pushdown automata (definition, design), non-deterministic and deterministic pushdown automata, relationship of pushdown automata with context free languages |
| 33 | 31/11/21 | 05:30pm | 1.0 hr | Section 8.1, section 8.2.1 of R4 | Pumping lemma for context free languages and linear languages, closure properties of context free languages |
| 34 | 31/11/21 | 05:30pm | 1.0 hr | Section 9.1 of R4 | Definition of Turing machine, Turing machine as language acceptors and transducers |
Last site update on
Oct 5, 2025 09:50:44 (UTC)