[go: up one dir, main page]
Scribd
Upload
38 views1 page

Flat Syllabus

The document outlines the syllabus for the B.Tech. course in Computer Science and Business Systems at E.G.S. Pillay Engineering College, focusing on Formal Language and Automata Theory. It covers topics such as regular languages, context-free languages, Turing machines, undecidability, and complexity theory over a total of 60 hours. The document also lists several key references for further study in the field.

Uploaded by

anandraj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
38 views1 page

Flat Syllabus

The document outlines the syllabus for the B.Tech. course in Computer Science and Business Systems at E.G.S. Pillay Engineering College, focusing on Formal Language and Automata Theory. It covers topics such as regular languages, context-free languages, Turing machines, undecidability, and complexity theory over a total of 60 hours. The document also lists several key references for further study in the field.

Uploaded by

anandraj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 1

B.Tech. - Computer Science and Business Systems | E.G.S.

Pillay Engineering College (Autonomous) | Regulations 2019


Approved in VI Academic Council Meeting held on 06-03-2021

1902BS301 FORMAL LANGUAGE AND AUTOMATA THEORY LTPC3104

MODULE I REGULAR LANGUAGES AND FINITE AUTOMATA 12 Hours


Alphabet-languages and grammars- Productions and derivation-Chomsky hierarchy of languages. Regular
expressions and languages- Deterministic finite automata (DFA) and equivalence with regular expressions
Nondeterministic finite automata (NFA) and equivalence with DFA- Regular grammars and equivalence with
finite automata - Properties of regular languages - Kleene‟s theorem - Pumping lemma for regular languages
Myhill- Nerode theorem and its uses- Minimization of finite automata.

MODULE II CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA 12 Hours


Context-free grammars (CFG) and languages (CFL)- Chomsky and Greibach normal forms - Nondeterministic
pushdown automata (PDA) and equivalence with CFG - Parse trees- Ambiguity in CFG - Pumping lemma for
context-free languages – Deterministic pushdown automata- Closure properties of CFLs.

MODULE III LINEAR BOUNDED AUTOMATA AND TURING MACHINES 12 Hours


Context-sensitive grammars (CSG) and languages - Linear bounded automata and equivalence with CSG. The
basic model for Turing machines (TM) - Turing recognizable (recursively enumerable) and Turing- decidable
(recursive) languages and their closure properties - Variants of Turing machines - Nondeterministic TMs and
equivalence with deterministic TMs - Unrestricted grammars and equivalence with Turing machines – TMs as
enumerators.

MODULE IV UNDECIDABILITY 12 Hours


Church-Turing thesis -Universal Turing machine – The universal and diagonalization languages - Reduction
between languages – Rice‟s theorem -Undecidable problems about languages.

MODULE V COMPLEXITY THEORY 12 Hours


Introductory ideas on Time complexity of deterministic and nondeterministic Turing machines - P and NP,NP
completeness - Cook‟s Theorem, other NP - Complete problems.
TOTAL: 60 HOURS

REFERENCES:
1. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages,
and Computation , Pearson Education, Third Edition, 2014.
2. Harry R. Lewis and Christos. H. Papadimitriou, Elements of The theory of Computation, Pearson
Education/PHI, 2007.
3. John C. Martin, Introduction to Languages and the Theory of Computation, TMH, 2007.
4. Micheal Sipser, Introduction of the Theory and Computation, Thomson Brokecole, 2005.
5. M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP
Completeness”, 1979.
6. https://nptel.ac.in.

You might also like