Formal Language and Automata Theory, August 2021 (CE)
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 | 09/08/21 | 12:15pm | 1.0 hr | - | A bird’s-eye view to formal language and automata theory |
| 2 | 16/08/21 | 12:55pm | 1.0 hr | Class Lecture | Introduction to automation, formal languages, grammar, formal models |
| 3 | 23/08/21 | 12:15pm | 1.0 hr | Class Lecture | Alphabets, strings, string operations, power of alphabet, languages, finite automata definition, example of a simple finite automata |
| 4 | 26/08/21 | 10:05am | 1.0 hr | Class Lecture | Definition of FA revisited, extended transition function, Examples to construct minimal DFA, String and language acceptance |
| 5 | 29/08/21 | 11:00am | 1.0 hr | Class Lecture | Some examples of minimal DFA construction |
| 6 | 02/09/21 | 04:10pm | 1.0 hr | Class Lecture | Examples of minimal DFA construction continued |
| 7 | 03/09/21 | 10:05am | 1.0 hr | Class Lecture | (Continued) Examples on minimal DFA formation |
| 8 | 13/09/21 | 12:15pm | 1.0 hr | Class Lecture | (Continued) Examples on minimal DFA, 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 |
| 9 | 16/09/21 | 04:00pm | 1.0 hr | Class Lecture | Representation on languages(verbal description, set notation, using grammars), Defintion of grammar: variables, terminals, start variable, production rules, language accepted by grammar, sentential forms of derivation, Examples on grammars and languages |
| 10 | 17/09/21 | 10:05pm | 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) |
| 11 | 20/09/21 | 12:15pm | 1.0 hr | Class Lecture | Non-deterministic finite acceptors (NFA): Definition, examples |
| 12 | 23/09/21 | 04:00pm | 1.0 hr | Class Lecture | Equivalence between NFA and DFA, Subset consctruction method from NFA to DFA, Examples |
| 13 | 24/09/21 | 10:05pm | 1.0 hr | Class Lecture | NFA with \( \epsilon \) moves (\( \epsilon \)-NFA), \( \epsilon \)-closure, examples on \( \epsilon \)-closure, Equivalence between \( \epsilon \)-NFA and NFA, example on the \( \epsilon \)-NFA and NFA equivalece |
| 14 | 27/09/21 | 12:15pm | 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 |
| 15 | 01/10/21 | 04:00pm | 1.0 hr | Class Lecture | Minimization of DFA: Table filling method, examples on table filling method |
| 16 | 04/10/21 | 12:15pm | - | - | Mid-semester (30 marks) |
| 17 | 08/10/21 | 04:00pm | 1.0 hr | Class Lecture | Finite automata with output, Introduction to Moore and Melay machine, Definition of Moore and Melay machine, Some examples to construct Moore machine |
| 18 | 25/10/21 | 12:15pm | 1.0 hr | Class Lecture | Examples on Melay machine |
| 19 | 27/10/21 | 09:00am | 1.0 hr | Class Lecture | Equivalence between Moore and Melay machine, Conversion from Moore to Melay and vice-versa |
| 20 | 29/10/21 | 10:05am | 1.0 hr | Class Lecture | Regular expression,Regular operators, precedence of operators, Examples of some basic regular expressions and the corresponding languages, Proofs on some special properties of empty language |
| 21 | 01/11/21 | 12:15pm | 1.0 hr | Refer to next class’s note | Problems on regular expression formation (1-20) |
| 22 | 12/11/21 | 10:05am | 1.0 hr | Class Lecture | Problems on regular expression formation (20-40) |
| 23 | 19/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 |
| 24 | 22/11/21 | 12:15pm | 1.0 hr | Class Lecture | State elimination method for FA to regular expression conversion, some examples on state elimination method |
| 25 | 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 |
| 26 | 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 |
| 27 | 26/11/21 | 05:30pm | 1.0 hr | Class Lecture | Examples on pumping lemma (continued … ) |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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
Apr 18, 2024 05:31:55 (UTC)