Year : 2024 (Jan-May)

Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

COURSE
PLAN

Target 45% (marks)

Level-1 35% (population)
Level-2 45% (population)
Level-3 55% (population)

1. Method of Evaluation

UG PG
Quizzes/Tests, Assignments (30%) Quizzes/Tests, Assignments, seminar (50%)
Mid Examination (20%) End semester (50%)
End examination
(50%)

2. Passing Criteria

Scale PG UG
Out of 10 point scale SGPA – “6.00” in each semester SGPA – “5.0” in each semester
CGPA – “6.00” CGPA – “5.0”
Min. Individual Course Grade – “C” Min. Individual Course Grade – “C”
Course Grade Point – “4.0” Course Grade Point – “4.0”
*for PG, passing marks are 40/100 in a paper
*for UG, passing marks are 35/100 in a paper

3. Pedagogy
 Presentations
 Flipped Classroom sessions
 Think-Pair-Share Activities
 Video Lectures
 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

4. References:

Text Books Web resources Reference books

1. John E. Hopcroft, Jeffery 1.http://www.cse.iitb.ac.in/
Ullman,”Introduction to Automata ~trivedi/courses/cs208/
theory Langauges & Narosa lecture01.pdf
computation” Publishers. 2.http://
2. K.L.P Mishra & www.cse.iitd.ernet.in/~sak/
N.Chandrasekaran,“Theory of Computer courses/toc/toc-recursive- 1. Daniel I.A. Cohen,“Introduction to
Science”, PHI Learning function-theory.pdf Computer Theory”,Wiley India.
3. John C Martin, “Introdution to 3.http:// 2. Kohavi,”Switching & Finite Automata
languages and theory of Computation”, textofvideo.nptel.iitm.ac.in/ Theory”,TMH
McGraw Hill 106106049/lec1.pdf
 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

GUIDELINES TO STUDY THE SUBJECT

Instructions to Students:
1. Go through the 'Syllabus' in the Black Board section of the web-site(https://learn.upes.ac.in) in order to
find out the Reading List.
2. Get your schedule and try to pace your studies as close to the timeline as possible.
3. Get your on-line lecture notes (Content, videos) at Lecture Notes section. These are our lecture notes.
Make sure you use them during this course.
4. Check your blackboard regularly
5. Go through study material
6. Check mails and announcements on blackboard
7. Keep updated with the posts, assignments and examinations which shall be conducted on the blackboard
8. Be regular, so that you do not suffer in any way
9. Cell Phones and other Electronic Communication Devices: Cell phones and other electronic
communication devices (such as Blackberries/Laptops) are not permitted in classes during Tests or the
Mid/Final Examination. Such devices MUST be turned off in the class room.
10. E-Mail and online learning tool: Each student in the class should have an e-mail id and a pass word to
access the LMS system regularly. Regularly, important information – Date of conducting class tests,
guest lectures, via online learning tool. The best way to arrange meetings with us or ask specific
questions is by email and prior appointment. All the assignments preferably should be uploaded on
online learning tool. Various research papers/reference material will be mailed/uploaded on online
learning platform time to time.
11. Attendance: Students are required to have minimum attendance of 75% in each subject. Students with
less than said percentage shall NOT be allowed to appear in the end semester examination.
This much should be enough to get you organized and on your way to having a great semester! If you need us
for anything, send your feedback through e-mail to your concerned faculty. Please use an appropriate subject
line to indicate your message details.
There will no doubt be many more activities in the coming weeks. So, to keep up to date with all the latest
developments, please keep visiting this website regularly.
 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

RELATED OUTCOMES

1. The expected outcomes of the Program are:

Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals,

PO1
and an engineering specialization to the solution of complex engineering problems.
Problem analysis: Identify, formulate, review research literature, and analyze complex engineering
PO2 problems reaching substantiated conclusions using first principles of mathematics, natural sciences,
and engineering sciences.
Design/development of solutions: Design solutions for complex engineering problems and design
PO3 system components or processes that meet the specified needs with appropriate consideration for
the public health and safety, and the cultural, societal, and environmental considerations.
Conduct investigations of complex problems: Use research-based knowledge and research methods
PO4 including design of experiments, analysis and interpretation of data, and synthesis of the information
to provide valid conclusions.
Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
PO5 engineering and IT tools including prediction and modeling to complex engineering activities with an
understanding of the limitations.
The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal,
PO6 health, safety, legal and cultural issues and the consequent responsibilities relevant to the
professional engineering practice.
Environment and sustainability: Understand the impact of the professional engineering solutions in
PO7 societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable
development.
Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of
PO8
the engineering practice.
Individual and team-work: Function effectively as an individual, and as a member or leader in diverse
PO9
teams, and in multidisciplinary settings.
Communication: Communicate effectively on complex engineering activities with the engineering
PO10 community and with society at-large, such as, being able to comprehend and write effective reports
and design documentation, make effective presentations, and give and receive clear instructions.
Project management and finance: Demonstrate knowledge and understanding of the engineering
PO11 and management principles and apply these to one’s own work, as a member and leader in a team,
to manage projects and in multidisciplinary environments.
PO12 Life-long learning: Recognize the need for, and have the preparation and ability to engage in
independent and life-long learning in the broadest context of technological change.

2. The expected outcomes of the Specific Program are:

Perform system and application programming using computer system concepts, concepts of Data
PSO1 Structures, algorithm development, problem solving and optimizing techniques.
 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

Apply software development and project management methodologies using concepts of front-end
PSO2 and back-end development and emerging technologies and platforms.
Apply computing knowledge to assess, design and propose cyber security solutions and perform
PSO3 forensic procedures on digital systems and cyber world using tools and technologies in the area of
cyber security and cyber forensics.

3. The expected outcomes of the Course are:

Apply formal mathematical methods to prove properties of languages, grammars and automata.
CO1

Design finite state machines for acceptance of strings.

CO2
CO3 Design context free grammar and push down automata for formal languages.
CO4 Construct Turing machine and distinguish between decidability and undecidability
CO-PO/PSO Relationship
4. Matrix

1- Slight (low) 2- Moderate (Medium) 3-Substantial (high)

PO
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
C
O
CO1 3 3 1 2 3 1
1

CO2 3 3 2 2 3 1
1

CO3 2 2 2 1 3 1
1

CO4 2 3 2 1 3 1
1

Average 2.6 2.6 1.6 1.8 3 1

5. Course Outcomes assessment plan:

Assign
CourseComponents Assign - - Quiz Quiz Quiz Quiz Quiz Test Mid End
Outcomes ment 1 ment 2 1 2 3 4 5 Semester Semester
CO1
CO2
CO3
CO4
CO5
 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

BROAD PLAN OF COURSE

COVERAGE
Course Activities:
Planned
S.No. Description No. of Remarks
From To
Sessions
Introduction to Defining Language, Kleene Closures,
Formal language theory , Arithmetic Expressions, Defining
Grammar, Chomsky Hierarchy, Transition Graph,
Generalized Transition Graph.

1. CO1

Automata Theory, Nondeterministic Finite Automata

(NFA), Deterministic Finite Automata (DFA), Construction
of DFA from NFA and Optimization, FA with Output: Moore
Machine, Mealy Machine and Equivalence, Applications
and Limitation of FA. Arden Theorem, Pumping Lemma for
regular expressions, Myhill-Nerode Theorem.
2. CO2
Context Free Grammar: Ambiguity, Simplification of CFGs,
Normal Forms for CFGs, Pumping Lemma for CFLs,
Decidability of CFGs, Ambiguous to Unambiguous CFG

3. CO2, CO3

Push Down Automata (PDA), Description and Definition,

Working of PDA, Acceptance of a String by PDA, PDA and
CFG, Introduction to auxiliary PDA and Two stack PDA.
4. Determinism and nondeterminism, Pumping Lemma. CO3
TM Basic Model, Definition and representation, Language
Acceptance by TM, TM and type 0 grammar, Halting
Problem of TM, Modifications in TM, Universal TM.
5. Language accepted by a TM, Role of TM, Design of TM CO4
CO4
Properties of Recursive and Recursively Enumerable
Languages, Unsolvable Decision Problem, Empty and non-
empty language, Rice theorem, Undecidability of Post
Correspondence Problem, Church's Thesis, halting
6. problem, Recursive Function Theory, Godel Numbering.

Sessions: Total No. of Instructional periods available for the course

 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

SESSION PLAN
A. DETAILED SESSION PLAN

NO. OF Assignme
SESSION CO nt(s)
TOPICS/SUB TOPICS
Addressed /Quizzes/
Tests
UNIT 1: Introduction to Finite Automata 5

Introduction to defining language, automata L1

Kleene closures L2
CO1
Finite Automata (FA) L3

Construction of FA Machines L4

Transition graph, generalized transition graph L5

UNIT 2: Nondeterministic finite Automata 7

(NFA), Deterministic Finite Automata (DFA)

Construction of NFA L6
Construction of NFA with E-moves L7

NFA with E-moves to without E-moves L8

NFA to DFA Conversion L9
CO2
Minimization of Automata L10

Finite State Transducer: Moore machine, Mealy L11

machine
Applications of Moore and Mealy Machines, L12
Limitations of FA
Assignment 1 | Test /Quiz 1
UNIT-3: Regular Expressions (RE), Regular 8
Languages, Context Free Grammar (CFG)
 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

Introduction to Regular Expressions (RE) and Regular L13

Languages.
Equivalence of FA With RE L14

Grammar Classification L15

CO2, CO3
Arden Theorem L16

Pumping Lemma for regular expressions, L17

Myhill-Nerode theorem L18

Mid Semester Examination

Context free grammar : Ambiguity, Simplification of L19

CFGs
Normal forms for CFGs, Pumping Lemma for CFLs, L20
Decidability of CFGs, Ambiguous to Unambiguous
CFG
UNIT-4: PUSHDOWN AUTOMATA (PDA) 5

Description and definition L21

Working of PDA, Acceptance of a string by PDA,PDA L22

and CFG CO3
Introduction to auxiliary PDA L23

Two stack PDA L24

Pumping Lemma L25
UNIT-5: Turing Machine TM 06

Basic model, definition L26

Representation, Language acceptance by TM L27

TM and type 0 grammar L28

CO4
Halting problem of TM, Modifications in TM L29

Universal TM L30

Language accepted by TM, Role of TM, Design of TM. L31

 Year : 2024 (Jan-May)
Semester : IV

1. Name of Faculty : Dr. Rohit Tanwar Course Code: CSEG 2035_3

: Formal Languages and Automata
2. Course Theory L: 3
3. Program : B.Tech. CSE all specializations T: 0
4. Target : 45% P: 0
C: 3

Assignment 2 | Test/Quiz 2

UNIT-6: Undecidability & Recursively Enumerable 05

Language
Properties of recursive and recursively enumerable L32
languages.
Unsolvable decision problem, Empty and Non L33
Empty language, rice theorem
CO4
Undecidability of Post correspondence problem L34

Church’s Thesis, Recursive function theory, L35

Gödel Numbering. L36

End Semester Exam

*9 lectures may be used for revision and doubt classes by the subject
faculty as per requirement.