Bihar Engineering University, Bihar, Information Technology Semester 4, Formal Language & Automata Theory Syllabus

Formal Language & 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 languages and grammars

1.3 Productions and derivation

1.4 Chomsky hierarchy of languages

1.5 Regular expressions and languages

1.6 Deterministic finite automata DFA and equivalence with regular expressions

1.7 Nondeterministic finite automata NFA and equivalence with DFA

1.8 Regular grammars and equivalence with finite automata

1.9 Properties of regular languages

1.10 Pumping lemma for regular languages

1.11 Minimization of finite automata

Unit - 2 Context-free languages and pushdown automata

Unit 2

Contextfree languages and pushdown automata

2.1 Contextfree grammars CFG and Contextfree languages CFL

2.2 Chomsky and Greibach normal forms

2.3 Nondeterministic pushdown automata PDA and equivalence with CFG

2.4 Parse trees

2.5 Ambiguity in CFG

2.6 Pumping lemma for contextfree languages

2.7 Deterministic pushdown automata

2.8 Closure properties of CFLs

Unit - 3 Context-sensitive languages

Unit 3

Contextsensitive languages

3.1 Contextsensitive grammars CSG and Context sensitive languages

3.2 Linear bounded automata and equivalence with CSG

Unit - 4 Turing machines

Unit 4

Turing machines

4.1 The basic model for Turing machines TM

4.2 Turing recognizable Recursively enumerable and Turingdecidable recursive languages and their closure properties

4.3 variants of Turing machines

4.4 Nondeterministic TMs and equivalence with deterministic TMs

4.5 Unrestricted grammars and equivalence with Turing machines

4.6 TMs as enumerators

Unit - 5 Undecidability

Unit 5

Undecidability

5.1 ChurchTuring thesis

5.2 Universal Turing machine

5.3 The universal and diagonalization languages

5.4 Reduction between languages and Rice’s theorem

5.5 Undecidable problems about languages

Download IT Sem 4 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-2
Machine learning
Database management system
Computer organization & architecture
Management i (organizational behaviour)
Popular posts
Top 10 free online resources to learn coding
What is machine learning
Top 10 jobs in information technology
An overview of object oriented programming
What is sorting algorithm
Share  
Link Copied
More than 1 Million students use Goseeko! Join them to feel the power of smart learning.
Spot anything incorrect? Contact us