The syllabus of Third Year (Computer Engineering) of Pune University is as follows:

Unit I
Basic Concepts and Formal Language theory:
Languages in abstract, Defining languages, Klenne closure, Symbol/alphabets,
string/word, Formal Introduction, mathematical foundation. Mathematical Formal Language Theory Representation for Formal Languages: Sets, Logic, Functions, Relations, Graphs, Proof Techniques-Formal Proofs, Inductive Proofs, Strings & Languages, examples, Basic Machine: Functionality and Limitations.

Importance of Automata Theory. Automata, Automata- Formal Definition &
Designing Finite Automata examples, Simplified Notation, Nondeterminism-Formal
Definition & Designing Nondeterministic Finite Automata, Computability &
Complexity, Pattern Matching. Language Acceptor: Concept, Machine as a language acceptor, example, Machine as a string processor. Finite Automata- Formal Definition & Designing Finite Automata –basic examples, Simplified Notation.

Regular Expressions and Languages:
Recursive definition of regular expression, regular set, identities of regular expressions, regular expressions, examples and FA. Equivalence of R.E.-examples.
Identity Rules And Algebraic laws for R.E. Regular languages and examples. Pumping lemma for regular languages. Limitations of R.E.

Unit II
Deterministic and Non deterministic Finite Automata: DFA: Definition and description of DFA, Transition Function of a DFA, NFA: Definition and description of DFA, Transition Function of a NFA, Є-NFA: Definition and description of NFA,
Transition Function of a NFA, Language acceptance by a FA(NFA , DFA) and string acceptance, Conversion of NFA with Є to NFA without Є, Conversion of NFA without Є to DFA, Conversion of NFA with Є to DFA (direct method and subset

construction method), Minimization of a DFA. Inter-conversion RE and FA: Construction of FA equivalent to RE using state loop elimination method. Construction of FA equivalent to RE using Andrsen’s Theorem. Construction of RE equivalent to FA(RE to Є-NFA, Є-NFA to DFA).

FA with output: Moore and Mealy machines -Definition, models, interconversion. Pumping Lemma for Regular languages, Properties of Regular Languages and FA: Closure and Decision properties, Limitations of FA.

Attached Files

Syllabus Third Year (Computer Engineering) of Pune University.pdf (239.0 KB, 68 views)