A Short Term Course on Cryptography

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,