Course Objectives:
To provide introduction to some of the central ideas of theoretical computer science from the perspective of formal languages.
To introduce the fundamental concepts of formal languages, grammars and automata theory.
Classify machines by their power to recognize languages.
Employ finite state machines to solve problems in computing.
To understand deterministic and non-deterministic machines.
To understand the differences between decidability and undecidability. Course Outcomes:
Able to understand the concept of abstract machines and their power to recognize the languages.
Able to employ finite state machines for modeling and solving computing problems.
Able to design context free grammars for formal languages.
Able to distinguish between decidability and undecidability.
Able to gain proficiency with mathematical tools and formal methods. UNIT – I
Introduction to Finite Automata: Structural Representations, Automata and Complexity, the Central Concepts of Automata Theory – Alphabets, Strings, Languages, Problems. Nondeterministic Finite Automata: Formal Definition, an application, Text Search, Finite Automata with Epsilon-Transitions.Deterministic Finite Automata: Definition of DFA, How A DFA Process Strings, The language of DFA, Conversion of NFA with €-transitions to NFA without €-transitions. Conversion of NFA to DFA, Moore and Melay machines UNIT – II
Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws for Regular Expressions, Conversion of Finite Automata to Regular Expressions. Pumping Lemma for Regular Languages, Statement of the pumping lemma, Applications of the Pumping Lemma. Closure Properties of Regular Languages: Closure properties of Regular languages, Decision Properties of Regular Languages, Equivalence and Minimization of Automata. UNIT – III
Context-Free Grammars: Definition of Context-Free Grammars, Derivations Using a Grammar, Leftmost and Rightmost Derivations, the Language of a Grammar, Sentential Forms, Parse Tress, Applications of Context-Free Grammars, Ambiguity in Grammars and Languages. Push Down Automata: Definition of the Pushdown Automaton, the Languages of a PDA, Equivalence of PDA’s and CFG’s, Acceptance by final state, Acceptance by empty stack,
Deterministic Pushdown Automata. From CFG to PDA, From PDA to CFG. UNIT – IV
Normal Forms for Context- Free Grammars: Eliminating useless symbols, Eliminating €- Productions. Chomsky Normal form Griebech Normal form. Pumping Lemma for Context-Free Languages: Statement of pumping lemma, Applications Closure Properties of Context-Free Languages: Closure properties of CFL’s, Decision Properties
of CFL’s Turing Machines: Introduction to Turing Machine, Formal Description, Instantaneous description,
The language of a Turing machine
UNIT – V
Types of Turing machine: Turing machines and halting Undecidability: Undecidability, A Language that is Not Recursively Enumerable, An Undecidable Problem That is RE, Undecidable Problems about Turing Machines, Recursive languages, Properties of recursive languages, Post’s Correspondence Problem, Modified Post Correspondence problem,Other Undecidable Problems, Counter machines. TEXT BOOKS:
1. Introduction to Automata Theory, Languages, and Computation, 3nd Edition, John E. Hopcroft,Rajeev Motwani, Jeffrey D. Ullman, Pearson Education.
2. Theory of Computer Science – Automata languages and computation, Mishra and Chandrashekaran, 2nd edition, PHI. REFERENCE BOOKS:
1. Introduction to Languages and The Theory of Computation, John C Martin, TMH.
2. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
3. A Text book on Automata Theory, P. K. Srimani, Nasir S. F. B, Cambridge University Press.
4. Introduction to the Theory of Computation, Michael Sipser, 3rd edition, Cengage Learning.
5. Introduction to Formal languages Automata Theory and Computation Kamala Krithivasan, Rama R, Pearson
CSE-AIML
SEMESTER
SUBJECT CODE
SUBJECT
Lession Plan Lecturer Notes & Question Bank
SYLLABUS
I
MA101BS
Mathematics – I
Click Here
I
AP102BS
Applied Physics
Click Here
I
CS103ES
Programming for Problem Solving
Click Here
I
ME104ES
Engineering Graphics
Click Here
I
AP105BS
Applied Physics Lab
Click Here
I
CS106ES
Programming for Problem Solving Lab
Click Here
I
MC109ES
Environmental Science
Click Here
II
MA201BS
Mathematics – II
Click Here
II
CH202BS
Chemistry
Click Here
II
EE203ES
Basic Electrical Engineering
Click Here
II
ME205ES
Engineering Workshop
Click Here
II
EN205HS
English
Click Here
II
CH206BS
Engineering Chemistry Lab
Click Here
II
EN207HS
English Language and Communication Skills Lab
Click Here
II
EE208ES
Basic Electrical Engineering Lab
Click Here
II-I
CS310PC
Discrete Mathematics
Click Here
II-I
CS302PC
Data Structures
Click Here
II-I
MA313BS
Mathematical and Statistical Foundations
Click Here
II-I
CS304PC
Computer Organization and Architecture
II-I
CS311PC
Python Programming
Click Here
II-I
SM306MS
Business Economics & Financial Analysis
Click Here
II-I
CS307PC
Data Structures Lab
Click Here
II-I
CS312PC
Python Programming Lab
Click Here
II-I
MC309
Gender Sensitization Lab
Click Here
II-II
CS416PC
Formal Language and Automata Theory
Click Here
II-II
CS417PC
Software Engineering
Click Here
II-II
CS403PC
Operating Systems
Click Here
II-II
CS404PC
Database Management Systems
Click Here
II-II
CS412PC
Object Oriented Programming using Java
Click Here
II-II
CS406PC
Operating Systems Lab
Click Here
II-II
CS407PC
Database Management Systems Lab
Click Here
II-II
CS408PC
Java Programming Lab
Click Here
II-II
MC409
Constitution of India
Click Here
III-I
Design and Analysis of Algorithms
Click Here
III-I
Machine Learning
Click Here
III-I
Computer Networks
Click Here
III-I
Compiler Design
Click Here
III-I
Graph Theory (PE1)
Click Here
III-I
Introduction to Data Science(PE1)
Click Here
III-I
Web Programming(PE1)
Click Here
III-I
Image Processing(PE1)
Click Here
III-I
Computer Graphics(PE1)
Click Here
III-I
Software Testing Methodologies(PE2)
Click Here
III-I
Information Retrieval Systems(PE2)
III-I
Pattern Recognition(PE2)
Click Here
III-I
Computer Vision and Robotics(PE2)
Click Here
Click Here
III-I
Data Warehousing and Business Intelligence(PE2)
Click Here
III-I
Machine Learning Lab
Click Here
III-I
Computer Networks Lab
Click Here
III-I
Advanced Communication Skills Lab
Click Here
III-I
Intellectual Property Rights
Click Here
III-II
Artificial Intelligence
Click Here
Click Here
III-II
DevOps
Click Here
Click Here
III-II
Natural Language Processing
Click Here
Click Here
III-II
Internet of Things(PE3)
Click Here
Click Here
III-II
Data Mining(PE3)
Click Here
Click Here
III-II
Scripting Languages(PE3)
Click Here
Click Here
III-II
Mobile Application Development(PE3)
Click Here
Click Here
III-II
Cryptography and Network Security(PE3)
Click Here
Click Here
III-II
Artificial Intelligence and Natural Language
Processing Lab
Add Comment