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, nondeterministic 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.

epsilonNFA

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 nonregular 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, kequivalents, 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, 2DFA, Instantaneous
description (ID), language accepted by a 2DFA, 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 nonregular 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, nondeterministic, 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, Kmap method, Gray code, implicant,
prime implicant, essential prime implicant, don't care conditions, examples,
nonuniqueness of minimal expression in case of don't care conditions, QuineMcCluskey method, finding cover, dominated row reduction,
dominating column reduction, examples 
62.

Combinational
circuit 
half adder,
full adder, half subtractor, full subtractor 
63.

Sequential
circuit 
Flipflops,
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 flipflop, implementing a modulo 8 binary counter
using T flipflop, implementing a modulo 8 binary counter using SR flipflop,
implementing a sequence detector using D flipflop, implementing a serial
paritybit generator using JK flipflop 
64.

Miminization of finite state machine 
Xsuccessor,
distinguishable state, distinguishable sequences, kdistinguishable 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, nonuniqueness 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 15: Lecture Note
·
Week 2: Lecture
610: Lecture Note
·
Week 3: Lecture
1115: Lecture Note
·
Week 4:
Lecture 1620: Lecture Note
·
Week 5:
Lecture 2125: Lecture Note
·
Week 6:
Lecture 2630: Lecture Note
·
Week 7: Lecture
3135: Lecture Note
·
Week 8: Lecture
3640: Lecture Note
·
Week 9:
Lecture 4145: Lecture Note
·
Week 10:
Lecture 4650: Lecture Note
·
Week 11:
Lecture 5155: Lecture Note
·
Week 12:
Lecture 5660: Lecture Note
·
Week 13: Lecture 61: Lecture
Note
·
Week 14: Lecture 6263:
Lecture Note
·
Week 15: Lecture 6465:
Lecture Note