mca Syllabus
Formal Language & Automata Theory
Code: CS402
Contacts: 3L+1T
Credits: 4
Prerequisites of Formal Language & Automata Theory:
Elementary discrete mathematics including the notion of set,function,relation,product,partial order,equivalence relation,graph& tree. They should have a thorough understanding of the principle of mathematical induction.
Module-1: [13 L]
Fundamentals: Basic definition of sequential circuit, block diagram, mathematical representation, concept of transition table and transition diagram (Relating of Automata concept to sequential circuit concept) Design of sequence detector, Introduction to finite state model [ 2L]
Finite state machine: Definitions, capability & state equivalent, kth- equivalent concept [ 1L]
Merger graph, Merger table, Compatibility graph [ 1L]
Finite memory definiteness, testing table & testing graph. [1L]
Deterministic finite automaton and non deterministic finite automaton. [1L] Transition diagrams and Language recognizers. [1L]
Finite Automata: NFA with I transitions - Significance, acceptance of languages. [1L]
Conversions and Equivalence: Equivalence between NFA with and without I transitions. NFA to DFA conversion. [2L]
Minimization of FSM, Equivalence between two FSM’s , Limitations of FSM [1L]
Application of finite automata, Finite Automata with output- Moore & Melay machine. [2L]
Learning outcome of Finite Automata:
The student will be able to define a system and recognize the behavior of a system. They will be able to minimize a system and compare different systems.
Module-2: [8 L]
Regular Languages : Regular sets. [1L]
Regular expressions, identity rules. Arden’s theorem state and prove [1L]
Constructing finite Automata for a given regular expressions, Regular string accepted by NFA/DFA [1L]
Pumping lemma of regular sets. Closure properties of regular sets (proofs not required). [1L]
Grammar Formalism: Regular grammars-right linear and left linear grammars. [1L]
Equivalence between regular linear grammar and FA. [1L]
Inter conversion, Context free grammar. [1L]
Derivation trees, sentential forms. Right most and leftmost derivation of strings. (Concept only) [1L]
Learning outcome of Regular Languages and Grammar:
Student will convert Finite Automata to regular expression. Students will be able to check equivalence between regular linear grammar and FA.
Module-3: [9L]
Context Free Grammars, Ambiguity in context free grammars. [1L]
Minimization of Context Free Grammars. [1L]
Chomsky normal form and Greibach normal form. [1L]
Pumping Lemma for Context Free Languages. [1L]
Enumeration of properties of CFL (proofs omitted). Closure property of CFL, Ogden’s lemma & its applications [1L]
Push Down Automata: Push down automata, definition. [1L]
Acceptance of CFL, Acceptance by final state and acceptance by empty state and its equivalence. [1L]
Equivalence of CFL and PDA, interconversion. (Proofs not required). [1L]
Introduction to DCFL and DPDA. [1L]
Learning outcome of PDA and context free grammar:
Students will be able to minimize context free grammar. Student will be able to check equivalence of CFL and PDA. They will be able to design Turing Machine.
Module-4: [6L]
Turing Machine : Turing Machine, definition, model [1L]
Design of TM, Computable functions [1L]
Church’s hypothesis, counter machine [1L]
Types of Turing machines (proofs not required) [1L]
Universal Turing Machine, Halting problem [2L]
Learning outcome of Turing Machine :
Students will be able to design Turing machine.
TEXT BOOKS:
“Introduction to Automata Theory Language and Computation”, Hopcroft H.E. and Ullman J. D., Pearson Education.
“Theory of Computer Science “, Automata Languages and computation”, Mishra and Chandrashekaran, 2nd edition, PHI.
“Formal Languages and Automata Theory”, C.K.Nagpal, Oxford
REFERENCES:
2.1 “Switching & Finite Automata”, ZVI Kohavi, 2nd Edn., Tata McGraw Hill
2.2 “Introduction to Computer Theory”, Daniel I.A. Cohen, John Wiley
2.3 “Introduction to languages and the Theory of Computation”, John C Martin, TMH
2.4 “Elements of Theory of Computation”, Lewis H.P. & Papadimitrou C.H. Pearson, PHI.
|
