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,

·

·

·

·

·

·

·

·

·

·

Ø

·

Ø

Ø

·

Ø

Ø

Ø

Ø

·

Ø

Ø

·

Ø

Ø

·

Ø

Ø