Flat Syllabus

MANAV RACHNA INTERNATIONAL INSTITUTE OF RESEARCH AND STUDIES
(Deemed to be University under section 3 of the UGC Act 1956)

NAAC 'A' Grade University
BCS-DS-502: Formal Languages & Automata Theory
Periods/week Credits Max. Marks : 200

L :3 T: 1 4.0 Continuous Evaluation :
100
Duration of Exam: 3 Hrs End Sem Examination
: 100
Pre-Requisite: NIL
Course Type: Program Core
Course Outcomes: Students will be able to-

BCS-DS-502.1. Recognize and manipulate the different concepts of formal languages
such as formal proofs, (non-)deterministic automata, regular expressions,
regular languages, context-free grammars, context-free languages, Turing
machines.
BCS-DS-502.2. Understand about the finite automata and conversion between
deterministic and non-deterministic finite automata.
BCS-DS-502.3. Prove and examine the properties of regular languages and automata
with rigorously formal mathematical methods.
BCS-DS-502.4. Analyze and design PDA for corresponding context-free grammars
accepting or generating a certain language.
BCS-DS-502.5. Evaluate and construct a TM for certain language.
BCS-DS-502.6. Specify the computability and tractability of various class of problems.
PART-A
Unit-1: Introduction to Formal languages
1.1 Overview: Alphabets, Strings & Languages, basic Definition of Grammar
1.2 Chomsky Classification of Languages: Regular, context free, unrestricted, Context
sensitive grammar and corresponding languages
1.3 Derivation & Languages generated by a Grammar
1.4 Relation between languages of classes.
Unit-2 Automata theory

2.1 Finite Automata, representation of FA.
2.2 Deterministic finite Automata (DFA) & Nondeterministic finite Automata (NDFA).
2.3 Subset Algorithm to convert NDFA to DFA , Minimization of Finite Automata.
2.4 Finite State Machine with output- Moore machine and Melay Machine.
2.5 Conversion of Moore machine to Melay Machine & Vice-Versa.
Unit-3: Regular languages

3.1 Regular Expressions
3.2 Equivalence of Finite Automata and Regular Expressions.
3.3 Regular expressions, identity rules, Arden’s theorem state and prove
3.4 Inter conversion of regular expression and FA.
3.5 The Pumping Lemma for Regular Sets, Applications of the pumping lemma
3.6 Closure properties of regular sets.
PART -B
Unit-4: Context Free languages and push down Automata
4.1 Properties of context free grammar, Definition, Context free.
4.2 Ambiguity in context free grammar, Derivation tree, application of Context free
Grammars.
4.3 Simplification of Context Free grammar Reduced forms Removal of useless Symbols
and unit
production.
4.4 Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) .
4.5 Pumping lemma for CFG.
4.6 Introduction to Push down Stack Machine Deterministic PDA, Non Deterministic PDA.
4.7 Acceptance of CFL, Acceptance by final state and acceptance by empty state.
4.8 Equivalence of CFL and PDA, interconversion.
Unit 5: Unrestricted language and Turing Machine

5.1 Unrestricted languages, Church–Turing thesis.
5.2 Turing Machine, definition, model.
5.3 Design of TM.
5.4 Variations of Turing Machines, Universal Turing Machine, Post Machine.
Unit-6: Computability and Intractability

6.1 Halting problem of Turing Machine.
6.2 Problem of Decidability and Undesirability , Examples of Undecidable problem.
6.3 Intractable Problems: The Classes P and NP, An NP-Complete Problem.
6.4 Post-Correspondence Problem.
6.5 Properties of Recursion and Recursively Enumerable Languages.
6.5 Rice’s theorem.
Text Books / Reference Books:

1. Hopcroaft J.E., Ullman, J.D., and Rajiv Motwani, 2001, Introduction to Automata
Theory, Language & Computations, 3rd Ed.,AW.
2. Mishra K.L.P.& N. Chandrasekaran, 2000, Theory of Computer Science Automata,
Languages and Computation,5th Ed. , 2000, PHI.
3. Peter Linz, 2001, Introduction to formal Languages & Automata, 3 rd Ed., Narosa Publ..
4. Deniel I.A. Cohen, 2000, Introduction to Computer Theory, 2 nd Ed., Wiley.
5. H.R. Lewis &C.H. Papaditriou, 1998, Elements of theory of Computation, 2 nd Ed., PHI.
6. Martin J.C , 2003, Introduction to Languages and Theory of Computation, 4 th Ed., TM
Software required/Weblinks:
www.vidyarthiplus.com/vp/thread_16699.html
www.cs.umb.edu/ppt/module8
Instructions for paper setting: Seven questions are to be set in total. First question will
be conceptual covering entire syllabus and will be compulsory to attempt. Three questions
will be set from each Part A and Part B (one from each unit) Student needs to attempt two
questions out of three from each part. Each question will be of 20 marks.
Distribution of Continuous Evaluation:

Sessional- I 30%
Sessional- II 30%
Assignment/Tutorial 20%
Class Work/
Performance 10%
Attendance 10%
Evaluation Tools:
Assignment/Tutorials
Sessional tests
Surprise questions during lectures/Class Performance
End Semester Examination
COURSE ARTICULATION MATRIX :

CO P P P P P P P P P P P P PS PS PS
Statement O O O O O O O O O O O O O O O
(BCS-DS- 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
502.1)
BCS-DS-502.1 2 2 1 3 3 1 1 1 2 2 2 2 2 2 2
BCS-DS-502.2 2 3 2 3 3 2 2 2 2 3 1 1 2 2 3
BCS-DS-502.3 1 2 2 2 2 2 1 1 3 2 1 1 3 1 3
BCS-DS-502.4 3 3 2 3 3 1 1 1 2 1 2 2 2 1 2
BCS-DS-502.5 2 1 1 2 1 2 2 1 2 1 1 3 3 3
BCS-DS-502.6 2 3 3 1 3 3 3 3 3 3 3 1 3 3

Flat Syllabus

Uploaded by

Copyright:

Available Formats

Flat Syllabus

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Flat Syllabus

Uploaded by

Copyright:

Available Formats

MANAV RACHNA INTERNATIONAL INSTITUTE OF RESEARCH AND STUDIES

(Deemed to be University under section 3 of the UGC Act 1956)

BCS-DS-502: Formal Languages & Automata Theory

Periods/week Credits Max. Marks : 200

Course Outcomes: Students will be able to-

Unit-2 Automata theory

Unit-3: Regular languages

Unit 5: Unrestricted language and Turing Machine

Unit-6: Computability and Intractability

Text Books / Reference Books:

Distribution of Continuous Evaluation:

COURSE ARTICULATION MATRIX :

You might also like