Deterministic Finite Automata (DFA)

Definition of DFA, finite set of states, finite input alphabet, transition function, starting/initial state, final/accepting state, examples of DFA


Input alphabet

Finite set of input symbols, binary alphabet, strings, empty string, length of a string, concatenation of two stings, power of alphabet set, set of all possible strings, languages


Extended transition function

How a DFA processing a string, extended transition function, examples


Language of DFA

Strings that accepted by a DFA, language of a DFA, regular languages, examples


Building DFA

Design a DFA to accepts the language, trial and error method, DFA with more than one final states, DFA corresponds to only one language, regular language can have many DFA that accept it


Building DFA (cont)

More examples on building DFA, DFA accepting the empty string, non-deterministic transition function


NFA (Nondeterministic Finite Automata)

Definition of NFA, nondeterministic transition functions, example of NFA, extended transition function over strings


Language of a NFA

Extended transition function for NFA, string accepted by NFA, Language of NFA, computation tree, accepting branch of computation tree


Equivalence of DFAs and NFAs

Building NFA for regular Language is easier than building a DFA, DFA as NFA, NFA accepts only regular languages, for every NFA we can construct an equivalence DFA (accepting the same language), subset construction


Subset Construction

NFA to DFA, subset construction, examples, Language of NFA is same as language of the DFA



Finite automata with epsilon moves, allows a transition on empty string, spontaneous transition without receiving an input symbol, definition of epsilon -NFA, examples.


Extended transition function of epsilon -NFA

Transition function and extended transition function of epsilon -NFA, string accepted by epsilon -NFA


Language of epsilon -NFA

Strings accepted by epsilon -NFA, examples, language of epsilon -NFA


epsilon -NFA to NFA

Equivalence of epsilon -NFA and NFA, epsilon NFA to NFA construction, example, epsilon NFA NFA DFA.


epsilon -NFA to DFA

Equivalence of epsilon -NFA and DFA, a variant of subset construction, example.


Regular expression

Regular expression and the language, recursive definition, examples


Regular expression (cont.)

Precedence between the operators of regular expression, examples, algebraic laws of the operators


More on regular expression

More algebraic properties of the operators of regular expression, examples, equivalence between regular expression and epsilon -NFA


Equivalence of epsilon -NFA and regular expression

Given a regular expression, there exists an epsilon -NFA which accepts the language of the regular expression, proof by induction on the number of operators used in the regular expression, base case


Equivalence of -NFA and regular expression (Cont)

Proof by the method of induction, example to construct an epsilon -NFA from a regular expression


DFA to Regular expression

DFA to regular expression, recursive definition of language between any two states with the intermediate states


DFA to Regular expression (Cont.)

Construction of regular expression from the DFA, proof by induction


Construction of regular expression from a DFA (example)

example of recursively constructing the regular expression from given DFA, equivalence between regular expression and finite automata


Closure properties of Regular Set

Regular sets (languages) are closed under: union, concatenation, Kleene closure, intersection. Construction of a DFA for intersection of two regular sets, union of two regular sets


Closure properties of Regular Set (Cont..)

Regular sets are closed under complements and reversal, complementing the final states of the DFA, proof of reversal using regular expression



Substitution mapping from one alphabet set to another alphabets, examples, the class of regular set is closed under substitution, homomorphism


Pumping Lemma

Properties of regular set, pumping lemma for regular language, necessary condition of a regular set


Application of the pumping lemma

Pumping lemma is a powerful tool for proving certain languages non regular, examples


More on Pumping lemma

More examples on non-regular language, algorithm to decide whether a regular set is empty, finite or infinite, equivalence of two DFA


Ardens Theorem

Identities of regular expressions, equation in regular expression, Arden theorem, application of Ardens theorem: DFA to regular expression


Minimization of FA

Minimization of DFA, equivalent states, k-equivalents, equivalence classes, example


Minimization of FA (Cont)

Finding the equivalence classes, collapsing the states in a equivalence class, tabular method of minimization, example


Two way FA

Two way finite automata, tape head moves left as well as right, 2-DFA, Instantaneous description (ID), language accepted by a 2-DFA, example


Finite automata with output

Moore machine, DFA is a special case of Moore machine, example of Moore machine, Mealy machine, example of mealy machine


Equivalence of Moore and Mealy machine

Moore and Mealy machines, construction of Mealy machine from Moore machine and Moore from Mealy machine


Context free grammars (CFG)

Definition of context free grammar (CFG), set of variables, set of terminals, set of productions/rules, example of CFG, derivations, language generated by a CFG, context free language (CFL), example of CFL


Context free language (CFL)

context free language (CFL), example of CFL, sentential form of a CFG, equivalent of two CFGs, example of a non-regular language which can be generated by a CFG


More example on CFL

More example of CFL, a language can be generated by more than one grammar, meaning of the name context free


More on CFG

Different types of production rules, example of CFG generating all integers, derivation tree


Derivation Tree/Parse Tree

Derivation tree or parse tree of a CFG, yield of the derivation tree, sentential form, more examples on yield and derivations


Leftmost and Rightmost derivations

Relationship between derivation trees and derivations, leftmost derivation, rightmost derivation


Ambiguity in CFG

More than two or more leftmost derivations and parse trees, ambiguous strings of terminals, ambiguous CFG, inherently ambiguous CFL, examples


Simplification of CFG

Eliminating the symbols of variable or terminals and rules which are not used in generating the language, Algo 1 to construct reduced grammars, examples


Algorithms to construct reduced grammar

Algo 1, algo 2 to find equivalent grammar in which every symbol (variable as well as terminal symbol) appear in some sentential form, Algo 3: Algo 1 + Algo 2


Elimination of Null and Unit productions

Elimination of null productions, equivalent grammar, example, elimination of unit productions, equivalent grammar, example


Chomsky Normal Form (CNF)

Chomsky normal form (CNF), example, reduction to CNF, example


Greibach Normal Form (GNF)

Greibach normal form (GNF), example, reduction to GNF, Lemma 1 and Lemma 2, example


Pushdown Automata (PDA)

Definition of pushdown automata (PDA), stack symbols, non-deterministic, example Instantaneous description (ID)


Language accepted by PDA

Move relation using ID, an illustration of move relation, reflexive and transitive closure of move relation, language accepted by a final state, language accepted by an empty stack (null stack)


Example of a language accepted by PDA

Language accepted by an empty stack, example, PDA halts when the stack is empty


Deterministic PDA

Nondeterministic PDA, language accepted by a PDA, deterministic PDA, example


Equivalence of language accepted

Equivalence of Language accepted by empty stack and language accepted by a final state, example


Equivalence PDA

Equivalence of Language accepted by final state and language accepted by an empty stack


Equivalence PDA and CFL

Construction of PDA from a CFG in GNF, example, alternative construction of PDA from a CFG in any form


Equivalence PDA and CFL (Cont)

Construction of a CFG from PDA accepting same language by empty stack, example


Relationship between regular language and CFL

All regular languages are CFLs but all CFLs are not regular, example, CFLs are closed under union, concatenation


Pumping lemma for CFLs

Pumping lemma for CFLs, necessary condition for a language to be regular, example of NON CFLs, CFLs are not closed under intersection


Closer properties of CFLs

CFL is closed under intersection with regular set, Construction of the PDA for the intersection, examples


Turning Machine

Turning machine as finite state machine, definition, blank symbol, writes on the tape, Instantaneous description (ID)


Language accepted by a Turning machine

Move relation in a Turing machine, string accepted by a Turing machine, language accepted by a Turing machine, example


Minimization of combinational circuits

minterm, maxterm, disjunctive normal form, sum of product, conjunctive normal form, product of sum, K-map method, Gray code, implicant, prime implicant, essential prime implicant, don't care conditions, examples, non-uniqueness of minimal expression in case of don't care conditions, Quine-McCluskey method, finding cover, dominated row reduction, dominating column reduction, examples


Combinational circuit

half adder, full adder, half subtractor, full subtractor


Sequential circuit

Flip-flops, characteristic table, excitation table, sequential circuit, logic diagram, logic equations, state diagram, converting a sequential circuit to a Mealy machine, example, converting a sequential circuit to a Moore machine, example, converting a Mealy machine to sequential circuit, implementing a serial binary adder using D flip-flop, implementing a modulo 8 binary counter using T flip-flop, implementing a modulo 8 binary counter using SR flip-flop, implementing a sequence detector using D flip-flop, implementing a serial parity-bit generator using JK flip-flop


Miminization of finite state machine

X-successor, distinguishable state, distinguishable sequences, k-distinguishable states, equivalent states, partition using distinguishing sequence of length k, Moore reduction procedure to get reduced quotient machine


Specification of incompletely specified machine

cover, compatible sates, non-uniqueness of minimal machine in case of incompletely specified machine, examples, augmented machine, Merger graph, Merger table, maximal compatibles, implied compatibles, closed set of compatibles, closed covering, finding minimal closed covering, compatibility graph,


      Week 1: Lecture 1-5: Lecture Note

      Week 2: Lecture 6-10: Lecture Note

      Week 3: Lecture 11-15: Lecture Note

      Week 4: Lecture 16-20: Lecture Note

      Week 5: Lecture 21-25: Lecture Note

      Week 6: Lecture 26-30: Lecture Note

      Week 7: Lecture 31-35: Lecture Note

      Week 8: Lecture 36-40: Lecture Note

      Week 9: Lecture 41-45: Lecture Note

      Week 10: Lecture 46-50: Lecture Note

Lecture Video 1

      Week 11: Lecture 51-55: Lecture Note

Lecture Video 1

Lecture Video 2

      Week 12: Lecture 56-60: Lecture Note

Lecture Video 1

Lecture Video 2

Lecture Video 3

Lecture Video 4

      Week 13: Lecture 61: Lecture Note

Lecture Video 1

Lecture Video 2

      Week 14: Lecture 62-63: Lecture Note

Lecture Video 1

Lecture Video 2

      Week 15: Lecture 64-65: Lecture Note

Lecture Video 1

Lecture Video 2