makaut
notes
Notes
PYQs
Menu
Notes
PYQs
← 4th Semester
Formal Language & Automata Theory
Code
PCC-CS403
Credits
3
Units
4
Topics
14
Buy for ₹99
or the 4th semester bundle, ₹249
Overview
Syllabus
Topics
Unit 1
Finite Automata
4 topics
1.1
DFA
1.2
NFA and conversion to DFA
1.3
Minimisation
1.4
Mealy and Moore machines
Unit 2
Regular Languages
3 topics
2.1
Regular expressions
2.2
Arden's theorem
2.3
Pumping lemma
Unit 3
Context Free Grammars
4 topics
3.1
Derivations and parse trees
3.2
Ambiguity
3.3
CNF and GNF
3.4
Pushdown automata
Unit 4
Turing Machines
3 topics
4.1
Turing machine design
4.2
Decidability
4.3
Halting problem