LECTURE

TOPIC

DESCRIPTION

1.        

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

2.        

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

3.        

Extended transition function

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

4.        

Language of DFA

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

5.        

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

6.        

Building DFA (cont…)

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

7.        

NFA (Nondeterministic Finite Automata)

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

8.        

Language of a NFA

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

9.        

Equivalence of DFA’s and NFA’s

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

10.     

Subset Construction

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

11.     

epsilon-NFA

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

12.     

Extended transition function of  epsilon -NFA

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

13.     

Language of  epsilon -NFA

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

14.     

epsilon -NFA to NFA

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

15.     

epsilon -NFA to DFA

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

16.     

Regular expression

Regular expression and the language, recursive definition,  examples

17.     

Regular expression (cont….)

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

18.     

More on regular expression

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

19.     

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

20.     

Equivalence of -NFA  and regular expression (Cont……)

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

21.     

DFA to Regular expression

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

22.     

DFA to Regular expression (Cont….)

Construction of regular expression from the DFA, proof by induction

23.     

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

24.     

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

25.     

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

26.     

Substitution

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

27.     

Pumping Lemma

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

28.     

Application of the pumping lemma

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

29.     

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

30.     

Arden’s Theorem

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

31.     

Minimization of FA

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

32.     

Minimization of FA (Cont…)

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

33.     

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

34.     

Finite automata with output

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

35.     

Equivalence of Moore and Mealy machine

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

36.     

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

37.     

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

38.     

More example on CFL

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

39.     

More on CFG

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

40.     

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

41.     

Leftmost and Rightmost derivations

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

42.     

Ambiguity in CFG

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

43.     

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

44.     

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

45.     

Elimination of Null and Unit productions

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

46.     

Chomsky Normal Form (CNF)

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

47.     

Greibach Normal Form (GNF)

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

48.     

Pushdown Automata (PDA)

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

49.     

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)

50.     

Example of a language accepted by PDA

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

51.     

Deterministic PDA

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

52.     

Equivalence of language accepted

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

53.     

Equivalence PDA

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

54.     

Equivalence PDA and CFL

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

55.     

Equivalence PDA and CFL (Cont……)

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

56.     

Relationship between regular language and CFL

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

57.     

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

58.     

Closer properties of CFLs

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

59.     

Turning Machine

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

60.     

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

61.     

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

62.     

Combinational circuit

half adder, full adder, half subtractor, full subtractor

63.     

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

64.     

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

65.     

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

 

 

 

Home