Biju Patnaik University of Technology, Odisha, Computer Engineering Semester 5, Formal Languages and Automata Theory Syllabus

Formal Languages and Automata Theory Lecture notes | Videos | Free pdf Download | Previous years solved question papers | MCQs | Question Banks| Syllabus
Get access to 100s of MCQs, Question banks, notes and videos as per your syllabus.
Try Now for free

Unit - 1 Introduction

Unit 1

Introduction

1.1 Alphabet

1.2 String

1.3 Languages

1.4 Automata

1.5 Grammar

1.6 Deterministic finite automation DFA Formal Definition

1.7 Simplified notation State transition graph

1.8 Transition table

1.9 Language of DFA

1.10 NonDeterministic Finite Automation NFA

1.11 NFA with epsilon transition

1.12 Language of NFA

1.13 Equivalence of DFA and NFA

1.14 Minimization of Finite Automata

1.15 Distinguishing one string from other

1.16 Myhill Nerode Theorem

Unit - 2 Regular Expression (RE)

Unit 2

Regular Expression RE

2.1 Definition

2.2 Operators of regular expression and their precedence

2.3 Algebraic laws for Regular expressions

2.4 Kleen’s Theorem

2.5 Regular expression to FA

2.6 DFA to Regular expression

2.7 Arden Theorem

2.8 NonRegular Languages

2.9 Pumping Lemma for regular Languages and its Application

2.10 Closure properties of Regular Languages

2.11 Decision properties of Regular Languages

2.12 Finite Automata with output Moore and Mealy machine

2.13 Equivalence of Moore and Mealy Machine

2.14 Applications and Limitation of FA

Unit - 3 Context Free Grammar (CFG) and Context Free Languages (CFL)

Unit – 3

Context Free Grammar CFG and Context Free Languages CFL

3.1 Definition

3.2 Examples

3.3 Derivation

3.4 Derivation Trees and Ambiguity

3.4 Inherent ambiguity

3.5 Ambiguous to Unambiguous CFG

3.6 Useless symbols

3.7 Simplification of CFG

3.8 Normal forms for CFGs CNF and GNF

3.9 Closure properties of CFLs

3.10 Decision Properties of CFLs Emptiness Finiteness and Membership

3.11 Pumping lemma for CFLs

Unit - 4 Push Down Automata (PDA)

Unit 4

Push Down Automata PDA

4.1 Description and definition

4.2 Instantaneous Description

4.3 Language of PDA

4.4 Acceptance by Final state

4.5 Acceptance by empty stack

4.6 Deterministic PDA

4.7 Equivalence of PDA and CFG

4.8 CFG to PDA and PDA to CFG

Unit - 5 Turing machines (TM)

Unit – 5

Turing Machine

5.1 Basic model definition and representation

5.2 Instantaneous Description

5.3 Language Acceptability by Turing Machines

5.4 Variants of Turing Machine

5.5 Turing Machine as Computer of Integer Functions

5.6 Universal Turing machine

5.7 Church’s Thesis

5.8 Recursive and Recursively Enumerable language

5.9 Halting Problem

5.10 Introduction to Undecidability

5.11 Undecidable problems about TMs

5.12 Post’s Correspondence Problem

5.13 Modified PCP

5.14 Introduction to Recursive Function Theory

Download CSE Sem 5 syllabus pdf
Get access to 100s of MCQs, Question banks, notes and videos as per your syllabus.
Try Now for free
Other Subjects of Semester-1
Operating systems
Database management systems
Artificial intelligence and machine learning
Popular posts
Top 10 free online resources to learn coding
What is machine learning
What is cloud computing
What is DBMS architecture
Sorting algorithm overview
Share  
Link Copied
More than 1 Million students use Goseeko! Join them to feel the power of smart learning.
Spot anything incorrect? Contact us