Lesson Plan Template

Course Information
Department COMPUTER SCIENCE AND ENGINEERING

Programme [Link]

Academic Year/Regulation 2025-2026,BR23

Semester III-1

Course Code 23CS5T09

Course Name FLAT

Credits 3

Faculty Name [Link]

Contact Hours/Week 12 WEEKS

Class III BETCH CSE-A,B,C

CO-PO-PSO-KP Mapping:
Mapped Mapped Knowledge
CO No. Course Outcome Statement BTL Mapped PO(s)
PSO(s) Profile(s)

CO1 BL2 PO1 PSO1 WK2, WK3

To Explain the fundamental concepts and need for
automata theory, including finite automata and transition
systems.

CO2 BL3 PO1, PO2 PSO1 WK2, WK4

To Apply the pumping lemma to analyze the regularity of
a given language.

CO3 BL3 PO1, PO2 PSO1 WK2, WK3

To Transform CFGs into Chomsky Normal Form (CNF)
and Greibach Normal Form (GNF).

CO4 BL3 PO1, PO3 PSO1, PSO2 WK4, WK5

To Design Pushdown Automata for simple context-free
languages and demonstrate their functioning.

CO5 BL4 PO2, PO11 PSO2 WK2, WK8

To Classify problems as decidable or undecidable, and

analyze examples such as the Halting Problem and Post’s
Correspondence Problem (PCP and Modified PCP).
Lesson Plan:
Intended Learning ILO Teaching Learning Assessment Remarks
Week Topic CO PO
Outcome (ILO) BTL Method Activity Tool
1 Need of Automata Recall the need and L1 CO1 PO1 Interactive Brainstorming Quiz Introduction
Theory importance of Lecture
Automata Theory.
Central Concepts Explain the central L2 CO1 PO1, Lecture + Concept Short Answer Basic
of Automata concepts of PO2 Discussion Mapping Questions Concepts
Theory Automata Theory.
Automaton Describe the concept L2 CO1 PO1 Lecture Class Quiz Basic Model
of an automaton. Discussion
Finite Automata Explain the structure L2 CO1 PO1, Lecture with State Diagram Assignment FA
and working of PO2 Examples Activity Fundamentals
Finite Automata.
Transition Illustrate transition L3 CO1 PO1, Demonstrati Diagram Class Test State
Systems systems using state PO2 on Construction Transitions
diagrams.
2 Acceptance of a Explain the process L2 CO1 PO1, Lecture Problem Quiz Language
String of string acceptance PO2 Solving Recognition
in finite automata.
Deterministic Construct DFA for L3 CO1 PO1, Problem DFA Design Assignment DFA
Finite Automata given regular PO2, Solving
(DFA) languages. PO3
Design of DFAs Design deterministic L3 CO1 PO1, Tutorial Design Worksheet DFA
finite automata for PO2, Exercise Construction
various problems. PO3
Non- Explain the concept L2 CO1 PO1, Lecture + State Diagram Quiz NFA
Deterministic and operation of PO2 Visualizatio Practice
Finite Automata NFA. n
(NFA)
Design of NFA Develop NFAs for L3 CO1 PO1, Practice NFA Design Assignment NFA
 given languages. PO2, Session Construction
PO3
3 Equivalence of Compare DFA and L4 CO1 PO1, Comparativ Comparative Class Test Equivalence
DFA and NFA NFA and prove their PO2, e Lecture Analysis
equivalence. PO4
Conversion of Convert NFA into L3 CO1 PO1, Problem Conversion Quiz Subset
NFA into DFA equivalent DFA PO2, Solving Exercise Construction
using subset PO3
construction.
Finite Automata Explain ε-NFA and L3 CO1 PO1, Lecture with ε-Closure Assignment ε-NFA
with ε-Transitions perform ε-closure PO2, Examples Activity
operations. PO3
Minimization of Apply minimization L4 CO1 PO1, Tutorial Minimization Class Test DFA
Finite Automata techniques to reduce PO2, Problems Optimization
DFA states. PO4
Mealy and Moore Differentiate Mealy L3 CO1 PO1, Interactive Machine Worksheet Output
Machines and Moore machines PO2, Lecture Design Activity Machines
and design output PO3
automata.
4 Applications and Summarize the L2 CO1 PO1, Discussion Case Study Assignment Unit-I Recap
Limitations of applications and PO2 Session
Finite Automata limitations of finite
automata.
Week Topic Intended Learning ILO CO PO Teaching Learning Assessment Remarks
Outcome (ILO) BTL Method Activity Tool
Regular Recall the concept L1 CO2 PO1 Interactive Brainstorming Quiz Introduction
Expressions and syntax of Lecture
Regular Expressions.
Regular Sets Explain the L2 CO2 PO1, Lecture + Concept Short Basic Concepts
properties of Regular PO2 Discussion Mapping Answer
Sets. Questions
Identity Rules Apply identity rules L3 CO2 PO1, Demonstration Exercise Assignment Simplification
 to simplify Regular PO2 Solving
Expressions.
Equivalence of Verify the L4 CO2 PO1, Lecture Comparative Quiz Equivalence
Two Regular equivalence of two PO2 Analysis
Expressions Regular Expressions.
5 Manipulations of Perform algebraic L3 CO2 PO1, Tutorial Problem Assignment RE
Regular manipulations on PO2 Solving Manipulation
Expressions Regular Expressions.
Finite Automata Explain the L2 CO2 PO1, Lecture with Class Quiz FA & RE
and Regular relationship between PO2 Examples Discussion
Expressions Finite Automata and
Regular Expressions.
Inter Conversion Convert Regular L3 CO2 PO1, Problem Conversion Worksheet Conversion
Expressions into PO2, Solving Activity
Finite Automata and PO3
vice versa.
Equivalence Demonstrate the L4 CO2 PO1, Comparative Comparative Class Test Equivalence
between FA and equivalence between PO2, Lecture Analysis
RE Finite Automata and PO4
Regular Expressions.
Pumping Lemma Explain and apply L4 CO2 PO1, Lecture with Proof Writing Assignment Pumping
of Regular Sets Pumping Lemma to PO2, Examples Lemma
prove non-regular PO4
languages.
6 Closure Properties Analyze the closure L4 CO2 PO1, Discussion Group Activity Quiz Closure
of Regular Sets properties of Regular PO2 Properties
Languages.
Grammars Describe the concept L2 CO2 PO1 Interactive Class Quiz Grammar
and components of Lecture Discussion Basics
Grammars.
Classification of Explain the L2 CO2 PO1, Lecture Classification Assignment Grammar
Grammars classification of PO2 Activity Types
 Grammars.
Chomsky Explain the Chomsky L3 CO2 PO1, Lecture with Hierarchy Class Test Chomsky
Hierarchy Hierarchy and its PO2, PPT Mapping Hierarchy
Theorem importance. PO3
Right Linear Construct Right L3 CO2 PO1, Tutorial Grammar Worksheet Right Linear
Regular Linear Regular PO2, Construction Grammar
Grammars Grammars for given PO3
languages.
7 Left Linear Construct Left Linear L3 CO2 PO1, Practice Grammar Assignment Left Linear
Regular Regular Grammars PO2, Session Design Grammar
Grammars for given languages. PO3
Equivalence Demonstrate the L4 CO2 PO1, Problem Conversion Quiz RG ↔ FA
between RG and equivalence between PO2, Solving Exercise
FA Regular Grammars PO3,
and Finite Automata. PO4
Inter Conversion Convert Regular L4 CO2 PO1, Tutorial Conversion
between RG and Grammars into Finite PO2, Practice
FA Automata and vice PO3,
versa. PO4
Week Topic Intended Learning ILO CO PO Teaching Learning Assessment Remarks
Outcome (ILO) BTL Method Activity Tool
Formal Languages Recall the concept L1 CO3 PO1 Interactive Brainstorming Quiz Introduction
and properties of Lecture
Formal Languages.
Context Free Explain the structure L2 CO3 PO1, Lecture + Grammar Short CFG Basics
Grammar (CFG) and components of PO2 Discussion Identification Answer
Context Free Questions
Grammar.
8 Leftmost Demonstrate leftmost L3 CO3 PO1, Demonstration Derivation Assignment Leftmost
Derivations derivation for given PO2 Exercise Derivation
CFGs.
Rightmost Demonstrate L3 CO3 PO1, Lecture with Problem Quiz Rightmost
 Derivations rightmost derivation PO2 Examples Solving Derivation
for given CFGs.
Parse Trees Construct parse trees L3 CO3 PO1, Tutorial Parse Tree Worksheet Parse Trees
for context free PO2, Construction
grammars. PO3
Ambiguous Identify and explain L4 CO3 PO1, Lecture Comparative Class Test Ambiguity
Grammars ambiguous PO2, Analysis
grammars. PO4
Elimination of Simplify CFGs by L4 CO3 PO1, Problem Grammar Assignment Simplification
Useless Symbols eliminating useless PO2, Solving Simplification
symbols. PO3
9 Elimination of ε- Remove ε- L4 CO3 PO1, Lecture with Simplification Quiz ε-Productions
Productions productions from PO2, Examples Activity
Context Free PO3
Grammars.
Elimination of Simplify CFGs by L4 CO3 PO1, Tutorial Grammar Worksheet Unit
Unit Productions eliminating unit PO2, Reduction Productions
productions. PO3
Simplification of Apply simplification L4 CO3 PO1, Practice Problem Assignment CFG
CFG techniques to PO2, Session Solving Simplification
Context Free PO3
Grammars.
Chomsky Normal Convert Context Free L3 CO3 PO1, Lecture CNF Quiz CNF
Form (CNF) Grammars into PO2, Conversion
Chomsky Normal PO3 Exercise
Form.
Greibach Normal Convert Context Free L3 CO3 PO1, Demonstration GNF Class Test GNF
Form (GNF) Grammars into PO2, Conversion
Greibach Normal PO3
Form.
10 Pumping Lemma Explain and apply L4 CO3 PO1, Lecture with Proof Writing Assignment Pumping
for Context Free Pumping Lemma for PO2, Examples Lemma
 Languages Context Free PO4
Languages.
Closure Properties Analyze closure L4 CO3 PO1, Discussion Group Activity Quiz Closure
of Context Free properties of Context PO2 Properties
Languages Free Languages.
Applications of Explain applications L2 CO3 PO1, Interactive Case Study Assignment Applications
Context Free of Context Free PO2 Lecture
Grammars Grammars in
compiler design and
language processing.
Unit-III Revision Summarize all L5 CO3 PO1, Revision Problem Unit Test Unit-III Recap
& Practice concepts of Unit-III PO2, Session Solving
and solve model PO3,
problems. PO4
Week Topic Intended Learning ILO CO PO Teaching Learning Assessment Remarks
Outcome (ILO) BTL Method Activity Tool
Pushdown Recall the concept L1 CO4 PO1 Interactive Brainstorming Quiz Introduction
Automata (PDA) and significance of Lecture
Pushdown Automata.
11 Definition of Explain the formal L2 CO4 PO1, Lecture + Class Short PDA Basics
Pushdown definition and PO2 Discussion Discussion Answer
Automata components of PDA. Questions
Model of Describe the working L2 CO4 PO1, Lecture with Model Assignment PDA Model
Pushdown model of Pushdown PO2 Examples Analysis
Automata Automata.
Graphical Illustrate Pushdown L3 CO4 PO1, Demonstration Diagram Quiz State Diagram
Notation Automata using PO2 Construction
graphical notation.
Instantaneous Explain the concept L3 CO4 PO1, Lecture Problem Class Test ID
Description (ID) of Instantaneous PO2 Solving Configuration
Description of PDA.
Language Describe different L2 CO4 PO1, Lecture + Group Quiz Acceptance
 Acceptance of methods of language PO2 Examples Discussion Criteria
PDA acceptance by PDA.
12 Design of Design PDA for L3 CO4 PO1, Problem PDA Design Assignment PDA
Pushdown Context Free PO2, Solving Exercise Construction
Automata Languages. PO3
Design Examples Construct PDA for L3 CO4 PO1, Tutorial Design Worksheet Design
of PDA balanced parentheses PO2, Practice Problems
and related problems. PO3
Deterministic Explain the concept L2 CO4 PO1, Interactive Comparative Quiz DPDA
Pushdown and characteristics of PO2 Lecture Study
Automata DPDA.
(DPDA)
Non-Deterministic Explain the concept L2 CO4 PO1, Lecture State Assignment NPDA
Pushdown and operation of PO2 Transition
Automata NPDA. Analysis
(NPDA)
Difference Compare L4 CO4 PO1, Comparative Comparative Class Test Comparison
between DPDA Deterministic and PO2, Lecture Analysis
and NPDA Non-Deterministic PO4
PDA.
13 Equivalence of Explain the L4 CO4 PO1, Lecture with Concept Quiz Equivalence
PDA and CFG equivalence between PO2, Examples Mapping
Pushdown Automata PO4
and Context Free
Grammars.
Conversion of Convert Context Free L3 CO4 PO1, Problem Conversion Assignment CFG → PDA
CFG to PDA Grammar into PO2, Solving Exercise
equivalent Pushdown PO3
Automata.
Conversion of Convert Pushdown L3 CO4 PO1, Tutorial Conversion Worksheet PDA → CFG
PDA to CFG Automata into PO2, Practice
equivalent Context PO3
 Free Grammar.
Two Stack Explain the concept L3 CO4 PO1, Lecture + Case Study Quiz Two Stack
Pushdown and applications of PO2, Discussion PDA
Automata Two Stack PO3
Pushdown Automata.
Applications of Summarize the L2 CO4 PO1, Discussion Case Study Assignment Unit-IV Recap
Pushdown applications of PDA PO2 Session
Automata in compiler design
and language
processing.
Week Topic Intended Learning ILO CO PO Teaching Learning Assessment Remarks
Outcome (ILO) BTL Method Activity Tool
14 Turing Machine Recall the concept L1 CO5 PO1 Interactive Brainstorming Quiz Introduction
(TM) and importance of Lecture
Turing Machines.
Definition of Explain the formal L2 CO5 PO1, Lecture + Class Short TM Basics
Turing Machine definition and PO2 Discussion Discussion Answer
components of a Questions
Turing Machine.
Model of Turing Describe the working L2 CO5 PO1, Lecture with Model Assignment TM Model
Machine model of a Turing PO2 Examples Analysis
Machine.
Representation of Explain the L3 CO5 PO1, Demonstration Configuration Quiz Instantaneous
TMs – representation and PO2 Analysis Description
Instantaneous instantaneous
Descriptions descriptions of
Turing Machines.
15 Transition Tables Construct transition L3 CO5 PO1, Problem Table Class Test Transition
tables for Turing PO2, Solving Construction Table
Machines. PO3
Transition Illustrate Turing L3 CO5 PO1, Lecture Diagram Assignment Transition
Diagrams Machines using PO2, Drawing Diagram
 transition diagrams. PO3
Language of a Explain language L2 CO5 PO1, Lecture with Problem Quiz Language
Turing Machine acceptance by a PO2 Examples Solving Acceptance
Turing Machine.
Design of Turing Design Turing L3 CO5 PO1, Tutorial TM Design Worksheet TM
Machines Machines for simple PO2, Activity Construction
computational PO3
problems.
Types of Turing Classify different L2 CO5 PO1, Interactive Comparative Assignment TM Types
Machines types of Turing PO2 Lecture Study
Machines.
16 Church's Thesis Explain Church's L2 CO5 PO1, Lecture Group Quiz Church's
Thesis and its PO2 Discussion Thesis
significance in
computation theory.
Universal Turing Describe the concept L3 CO5 PO1, Lecture with Concept Class Test Universal TM
Machine and operation of PO2, PPT Mapping
Universal Turing PO3
Machine.
Restricted Turing Explain Restricted L2 CO5 PO1, Lecture Case Study Assignment Restricted TM
Machine Turing Machine and PO2
its applications.
Decidable Explain decidable L3 CO5 PO1, Lecture Problem Quiz Decidability
Problems problems and their PO2, Analysis
characteristics. PO4
Undecidable Analyze undecidable L4 CO5 PO1, Discussion Comparative Class Test Undecidability
Problems problems in PO2, Analysis
computation theory. PO4
17 Halting Problem Explain the Halting L4 CO5 PO1, Lecture with Proof Writing Assignment Halting
Problem and prove PO2, Examples Problem
its undecidability. PO4
Post's Explain Post's L3 CO5 PO1, Tutorial Problem Worksheet PCP
 Correspondence Correspondence PO2, Solving
Problem (PCP) Problem and its PO3
significance.
Modified Post's Analyze Modified L4 CO5 PO1, Lecture Comparative Quiz Modified PCP
Correspondence PCP and distinguish PO2, Analysis
Problem it from PCP. PO4
Class P and NP Explain the concepts L2 CO5 PO1, Interactive Class Assignment Complexity
of P and NP PO2 Lecture Discussion Classes
complexity classes.
NP-Hard Describe NP-Hard L3 CO5 PO1, Lecture with Case Study Quiz NP-Hard
Problems problems with PO2, Examples
suitable examples. PO3
NP-Complete Explain NP- L4 CO5 PO1, Revision Problem Unit Test Unit-V Recap
Problems Complete problems PO2, Session Solving &
and summarize Unit- PO3, Discussion
V concepts. PO4

Program Outcomes (PO)

PO Program Outcome Predominant BTL
PO1 Engineering Knowledge L3 - Apply
PO2 Problem Analysis L4 - Analyze
PO3 Design / Development of Solutions L6 - Create
 PO4 Investigation L5 - Evaluate
PO5 Engineering Practice L3-Apply-Analyze
PO6 Engineer and the World L5 - Evaluate
PO7 Ethics L5 - Evaluate
PO8 Individual and Collaborative Team Work L3 - Apply
PO9 Communication L3 - Apply
PO10 Project Management and Finance L4- Analyze-Evaluate
PO11 Life-long Learning L5-Evaluate-Create

Program Specific Outcomes(PSOs)

1.
2.

Knowledge profiles:
WK Knowledge Profile Description
Understanding and application of natural sciences relevant to
WK1 Natural Sciences
engineering.
 Mathematics, Statistics and Application of mathematics, statistics and computing concepts.
WK2
Computing Fundamentals
WK3 Engineering Fundamentals Core engineering principles and theories.
Specialized Engineering Advanced knowledge in the engineering discipline.
WK4
Knowledge
WK5 Engineering Design Knowledge required for engineering design and solution development.
WK6 Engineering Practice Engineering tools, standards and professional practice.
WK7 Role of Engineering in Society Societal, legal, cultural and safety considerations.
WK8 Research and Investigation Experimental methods, data analysis and research techniques.
WK9 Sustainability Sustainable development and environmental stewardship.

Attainment Targets:

CO Targeted level of Proficiency Targeted Level of Attainment

CO1 80% ≥10 3

CO2 70%≥10 2
CO3 70%≥10 2
CO4 50%≥10 1
CO5 80%≥10 3